Προβλήματα Μαθηματικών

Ιουλίου 24, 2008

Σφαιρίδια

Filed under: Λυμένα Προβλήματα,Με υπόδειξη — Themis Mitsis @ 8:39 μμ

Με πόσους διαφορετικούς τρόπους μπορείτε να βάλετε k όμοια σφαιρίδια σε n διακεκριμένα δοχεία χωρητικότητας m_1,\dots,m_n το καθένα;

(k\leq m_1+\cdots+m_n)

Advertisements

8 Σχόλια »

  1. Υπόδειξη:

    Υπάρχουν πολλοί τρόποι να προσεγγίσετε το πρόβλημα. Όποιον κι’ αν ακολουθήσετε, καλό είναι πρώτα να δώσετε μια λύση στην απλούστερη περίπτωση όπου τα δοχεία δεν έχουν περιορισμένη χωρητικότητα.

    Μου αρέσει!

    Σχόλιο από Themis Mitsis — Ιουλίου 31, 2008 @ 6:26 μμ

  2. Άν δεν είχαμε περιορισμό στις χωρητικότητες των κουτιών τότε θα δουλεύαμε ως εξής:
    έχουμε {k} αντικείμενα και για το καθένα έχουμε {n} επιλογές για το σε ποιό κουτί θα το τοποθετήσουμε. Άρα
    συνολικά {n^k} τρόπους να τοποθετηθούν.

    Το πρόβλημα θα ήταν πιο εύκολο αν τα k αντικείμενα ήταν διακεκριμένα μεταξύ τους και ακόμα
    {k=m_{1}+m_{2}+\cdots +m_{n}}
    Τότε θα λυνόταν ως εξής: Παίρνουμε ολες τις μεταθέσεις των k αντικειμένων και διαιρούμε με τις μεταθέσεις στα εσωτερικά των κουτιών. (Σαν να έχουμε τοποθετήσει τα κουτιά κατω απο τα σφαιρίδια και να τα αφήνουμε να πέσουν έπειτα απο κάθε μετάθεση, τέλος διαιρούμε με τις μεταθέσεις στα εσωτερικά των κουτιών επειδή δεν μας ενδιαφέρει η εσωτερική διάταξη στα κουτιά)

    Εδώ που τα σφαιρίδια είναι ίδια και {k<= m_{1}+m_{2}+ \cdots + m_{n}}
    ορίζουμε {s= m_{1}+m_{2}+ \cdots +m_{n} - k}  που είναι οι κενές θέσεις και έχουμε:

    \displaystyle {{(k+s)!}  \over {{k}!{s}!{m_{1}}!{m_{2}}!\ldots{m_{n}}!}}

    Όπου έχουμε πάρει όλες τις μεταθέσεις των {k+s} αντικειμένων (σφαιριδίων και κενών μαζί), έχουμε διαιρέσει με τις μεταθέσεις των σφαιριδίων αφου είναι ολα ίδια, το ίδιο έχουμε κάνει και για τα κενά και τέλος έχουμε διαιρέσει με τις εσωτερικές μεταθέσεις στα {m_{1}\cdots m_{n}} αφού δεν μας ενδιαφέρει η εσωτερική διάταξη στο κάθε κουτί.

    Μου αρέσει!

    Σχόλιο από georgepapakir — Δεκέμβριος 2, 2008 @ 8:54 μμ

  3. Ο τύπος στον οποίο καταλήγεις δεν είναι σωστός. Δεν σου δίνει την ακόλουθη ειδική περίπτωση: Πάρε
    m_1=m_2=\cdots=m_n=k,
    δηλαδή δεν υπάρχει περιορισμός στην χωρητικότητα των δοχείων. Τότε η απάντηση είναι
    \binom{n+k-1}{k}, το οποίο δεν συμφωνεί με τον τύπο που δίνεις.

    Μου αρέσει!

    Σχόλιο από Themis Mitsis — Δεκέμβριος 3, 2008 @ 5:01 μμ

  4. Καλησπέρα! Η ιδέα που είχα είναι η εξής : Αν $ x_i $ το πλήθος των σφαριδίων στο i δοχείο , τότε ψάχνουμε το πλήθος των λύσεων της διοφαντικής εξίσωσης $ x_1+x_2+..+x_n=k $ κάτω από τους περιορισμούς $ 0<=x_ia_i $ ειναι $ \binom{k-\sum_{i}a_i -1}{n-1} $.

    Μου αρέσει!

    Σχόλιο από nixmtp — Σεπτεμβρίου 8, 2011 @ 3:16 μμ

  5. Καλησπέρα! Η ιδέα που είχα είναι η εξής : Αν x_i το πλήθος των σφαριδίων στο i δοχείο , τότε ψάχνουμε το πλήθος των λύσεων της διοφαντικής εξίσωσης x_1+x_2+..+x_n=k κάτω από τους περιορισμούς 0<=x_ia_i ειναι \binom{k-\sum_{i}a_i -1}{n-1} .

    Μου αρέσει!

    Σχόλιο από nixmtp — Σεπτεμβρίου 8, 2011 @ 3:17 μμ

  6. .. κάτω απο τους περιορισμούς 0\leq x_i\leq m_i .
    Η αρχή inclusion-exclusion θα δώσει ότι το ζητούμενο πλήθος είναι \binom{k+n-1}{n-1} -\sum_{i}\binom{k-m_i+n-2}{n-1}+\sum_{i,j}\binom{k-m_i-m_j+n-3}{n-1}+\cdots+(-1)^k\binom{k-m_1-m_2-...-m_n-1}{n-1} όπου εν γένει η άθροιση συνεχίζεται μέχρι να εμφανιστούν μηδενικοί όροι. Η βασική παρατήρηση που χρειάζεται στην εφαρμογή inclusion-exclusion είναι ότι το πλήθος των λύσεων της διοφαντικής x_1+...+x_n =k , x_i>a_i ειναι \binom{k-\sum_{i}a_i -1}{n-1} .

    Μου αρέσει!

    Σχόλιο από nixmtp — Σεπτεμβρίου 8, 2011 @ 3:19 μμ

  7. διόρθωση : (-1)^n στο άθροισμα στη θέση του (-1)^k

    Μου αρέσει!

    Σχόλιο από nixmtp — Σεπτεμβρίου 8, 2011 @ 5:35 μμ

  8. Σωστά.

    Μου αρέσει!

    Σχόλιο από Themis Mitsis — Σεπτεμβρίου 8, 2011 @ 10:39 μμ


RSS feed for comments on this post. TrackBack URI

Σχολιάστε

Συνδεθείτε για να δημοσιεύσετε το σχόλιο σας:

Λογότυπο WordPress.com

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό WordPress.com. Αποσύνδεση / Αλλαγή )

Φωτογραφία Twitter

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό Twitter. Αποσύνδεση / Αλλαγή )

Φωτογραφία Facebook

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό Facebook. Αποσύνδεση / Αλλαγή )

Φωτογραφία Google+

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό Google+. Αποσύνδεση / Αλλαγή )

Σύνδεση με %s

Δημιουργήστε ένα δωρεάν ιστότοπο ή ιστολόγιο στο WordPress.com.

Αρέσει σε %d bloggers: