Πρόβλημα του Γαλιλαίου

Συντονιστές: cretanman, Demetres, polysot, achilleas, socrates, silouan

kwstas12345
Δημοσιεύσεις: 1055
Εγγραφή: Δευ Ιαν 11, 2010 2:12 pm

Πρόβλημα του Γαλιλαίου

#1

Μη αναγνωσμένη δημοσίευση από kwstas12345 » Κυρ Σεπ 18, 2011 1:27 pm

Έστω \displaystyle \mathcal{H}\left(n,k \right) ο αριθμός των δυνατών αποτελεσμάτων ρίψης n διακεκριμένων κύβων σε καθένα από τα οποία το άθροισμα των εδρών είναι ίσο με k. Να αποδείξετε ότι: \displaystyle \mathcal{H}\left(n,k \right)=\sum_{m=0}^{s}{\left(-1 \right)^m \binom{n}{m}\binom{k-6m-1}{n-1}} όπου \displaystyle s=\displaystyle{\lfloor \frac{k-n}{6} \rfloor}.


dement
Διευθύνον Μέλος
Δημοσιεύσεις: 1405
Εγγραφή: Τρί Δεκ 23, 2008 10:11 am

Re: Πρόβλημα του Γαλιλαίου

#2

Μη αναγνωσμένη δημοσίευση από dement » Δευ Σεπ 19, 2011 3:44 pm

Κάθε συνδυασμός του \mathcal{H} (n,k) μπορεί να προκύψει από έναν συνδυασμό του \mathcal{H} (n,k-1), προσθέτοντας 1 στο αποτέλεσμα του τελευταίου ζαριού...

... εκτός από τους \mathcal{H} (n-1,k-7) συνδυασμούς όπου το τελευταίο ζάρι φέρνει 6...

... και σε αυτό πρέπει να προσθέσουμε τους \mathcal{H} (n-1,k-1) συνδυασμούς όπου το τελευταίο ζάρι φέρνει 1.

Ετσι έχουμε \mathcal{H} (n,k) = \mathcal{H} (n,k-1) + \mathcal{H} (n-1,k-1) - \mathcal{H} (n-1,k-7) για n \geq 2 και χρησιμοποιούμε επαγωγή ως προς n.

Για n=1 έχουμε \mathcal{H} (n,k) = 1 αν 1 \leq k \leq 6, αλλιώς 0. Ο τύπος ισχύει γιατί αν k \leq 0 τότε το άθροισμα δεν έχει όρους, ενώ αν k > 6 το άθροισμα γίνεται 1 - 1 = 0. Θέτουμε \displaystyle s = \left\lfloor \frac{k-n}{6} \right\rfloor.

Επίσης \mathcal{H} (n,1) = \delta_{n1} και πάλι ο τύπος ισχύει.

Στη συνέχεια έχουμε \displaystyle \mathcal{H} (n,k) = \mathcal{H} (n,k-1) + \mathcal{H} (n-1,k-1) - \mathcal{H} (n-1,k-7) =

\displaystyle = \sum_{m=0}^s (-1)^m \binom{n}{m} \binom{k-6m-2}{n-1} + \sum_{m=0}^s (-1)^m \binom{n-1}{m} \binom{k-6m-2}{n-2} - \sum_{m=0}^{s-1} (-1)^m \binom{n-1}{m} \binom{k-6m-8}{n-2} =

\displaystyle = \sum_{m=0}^s (-1)^m \binom{n}{m} \binom{k-6m-2}{n-1} + \sum_{m=0}^s (-1)^m \binom{n-1}{m} \binom{k-6m-2}{n-2} + \sum_{m=1}^s (-1)^m \binom{n-1}{m-1} \binom{k-6m-2}{n-2} =

\displaystyle = \sum_{m=0}^s (-1)^m \binom{n}{m} \binom{k-6m-2}{n-1} + \sum_{m=0}^s (-1)^m \binom{n}{m} \binom{k-6m-2}{n-2} = \sum_{m=0}^s (-1)^m \binom{n}{m} \binom{k-6m-1}{n-1} και τέλος.


Δημήτρης Σκουτέρης

Τα μαθηματικά είναι η μοναδική επιστήμη που θα μπορούσε κανείς να εξακολουθήσει να ασκεί αν κάποτε ξυπνούσε και το σύμπαν δεν υπήρχε πλέον.
Άβαταρ μέλους
Demetres
Γενικός Συντονιστής
Δημοσιεύσεις: 8447
Εγγραφή: Δευ Ιαν 19, 2009 5:16 pm
Τοποθεσία: Λεμεσός/Πύλα
Επικοινωνία:

Re: Πρόβλημα του Γαλιλαίου

#3

Μη αναγνωσμένη δημοσίευση από Demetres » Δευ Σεπ 19, 2011 4:03 pm

Διαφορετικά, το \mathcal{H}(n,k) είναι ο συντελεστής του x^k στο ανάπτυγμα (x + x^2 + \cdots + x^6)^n. Ισοδύναμα, είναι ο συντελεστής του x^{k-n} στο ανάπτυγμα \displaystyle{ (1 + x + x^2 + \cdots + x^5)^n = \frac{(1-x^6)^n}{(1-x)^n} = (1-x^6)^n(1 + x + x^2 + \cdots)^n.}

Ας υπολογίσουμε πρώτα τον συντελεστή του x^r στο ανάπτυγμα (1 + x + x^2 + \cdots)^n. Αυτό ισούται με τον αριθμό των λύσεων της εξίσωσης x_1 + \cdots + x_n = r σε μη αρνητικούς ακεραίους και είναι γνωστό πως ισούται με \displaystyle{ \binom{r+n-1}{r-1}.} [Σκιαγράφηση απόδειξης: Κάθε «λέξη» με r - και n-1 | αντιστοιχεί σε μια λύση της πιο πάνω εξίσωσης και αντιστρόφως. Π.χ. η λέξη ---||--|-|-- αντιστοιχεί στο 3 + 0 + 2 + 1 + 2 = 8.]


Οι μόνοι τρόποι για να πάρουμε όρους της μορφής x^{k-n} στο ανάπτυγμα του, είναι να πάρουμε κάποιο όρο της μορφής x^{6m} από το (1-x^6)^n και κάποιο όρο της μορφής x^{k-n-6m} από το (1 + x + x^2 + \cdots)^n όπου απαραίτητα πρέπει o m να είναι μη αρνητικός ακέραιος με k - n \geqslant 6m. Επομένως έχουμε

\displaystyle{\mathcal{H}(n,k) = \sum_{m=0}^s (-1)^m \binom{n}{m} \binom{k-n-6m + n -1}{n-1} = \sum_{m}^s (-1)^m \binom{n}{m} \binom{k-6m -1}{n-1}}


kwstas12345
Δημοσιεύσεις: 1055
Εγγραφή: Δευ Ιαν 11, 2010 2:12 pm

Re: Πρόβλημα του Γαλιλαίου

#4

Μη αναγνωσμένη δημοσίευση από kwstas12345 » Δευ Σεπ 19, 2011 5:12 pm

Μια άλλη γνωστή μέθοδος, χρησιμοποιεί την αρχή του εγκλεισμού-αποκλεισμού και είναι ιδιαιτερα διδακτική. Άς πούμε \displaystyle x_{i} \in \left\{1,2,...,6 \right\} την ένδειξη του ζαριού. Ουσιαστικά o \displaystyle \mathcal {H}\left(n,k \right) είναι το πλήθος των θετικών και ακέραιων

λύσεων της εξίσωσης \displaystyle x_{1}+x_{2}+...+x_{n}=k υπό τον περιορισμό \displaystyle x_{i} \leqslant 6. Άς θεωρήσουμε \displaystyle A_{i} το σύνολο των λύσεων όπου \displaystyle x_{i}>6 τότε \displaystyle \mathcal{H}\left(n,k \right)=\left|\left(\bigcup_{i=1}^{n}{A_{i}} \right){'} \right|=\left|\bigcap_{i=1}^{n}{A_{i}{'}} \right|

όπου \displaystyle \left|B \right| είναι ο πληθικός αριθμός του B. Όμως από την αρχή του εγκλεισμού αποκλεισμού \displaystyle \left|\bigcap_{i=1}^{n}{A_{i}{'}} \right|=\sum_{i=0}^{n}{\left(-1 \right)^{i}S_{n,i}} με \displaystyle {S_{n,i}}=\sum{\left|\bigcap_{j=1}^{m}{A_{d_{j}}} \right|} όπου η άθροιση εκτέινεται σε όλους τους συνδυασμούς \displaystyle \left\{d_{1},d_{2},..,d_{m} \right\} των δεικτών \displaystyle \left\{1,2,...,n \right\}.

Από γνωστό τύπο το σύνολο των θετικών ακέραιων λύσεων της αρχικής εξίσωσης είναι \displaystyle \binom{k-1}{n-1} ενώ οι λύσεις της αρχικής γενικά υπό τον περιορισμό \displaystyle x_{i}> s λοπου ο προηγούμενος πριορισμός πρόκειται για m μεταβλητές

είναι \displaystyle \binom{k-6m-1}{n-1} \displaystyle ,m=1,2,..., s ενώ για \displaystyle s,s+1,...,n είναι 0. Συνεπώς στην περίπτωση που ακριβώς m από τις μεταβλητές είναι μεγαλύτερες του 6, αυτές τις m μεταβλητές τις παίρνουμε κατά \displaystyle\binom{n}{m} τρόπους

και για κάθε μια εκλογή αυτών έχουμε \displaystyle \binom{k-6m-1}{n-1} λύσεις και έτσι: \displaystyle S_{n,m}=\binom{n}{m} \binom{k-6m-1}{n-1}.'Ετσι \displaystyle \mathcal{H}\left(n,k \right)=\binom{n-1}{k-1}+\sum_{m=1}^{s}{\left(-1 \right)^m\binom{n}{m}\binom{k-6m-1}{n-1}}=\sum_{m=0}^{s}{\left(-1 \right)^m\binom{n}{m}\binom{k-6m-1}{n-1}}.

Να τονίσουμε ότι η παραπάνω μέθοδος μπορεί να χρησιμοποιθεί για την απόδειξη αρκετών ταυτοτήτων.

Edit: Επειδή τα σύνολα \displaystyle A_{1},A_{2},...,A_{n} είναι ανταλάξιμα (στην περιπτωσή μας o: \displaystyle \left|\bigcap_{j=1}^{m}{A_{i_{j}}} \right|=\binom{k-6m-1}{n-1}) εξαρτάται μόνο από το m ισχυει κατευθείαν \displaystyle \left|\left(\bigcup_{i=0}^{n}{A_{i}} \right){'} \right|=\sum_{m=0}^{n}{\left(-1 \right)^m \binom{n}{m} \left|\bigcap_{j=1}^{m}{A_{i_{j}}} \right|}

όπου η άθροιση εκτείνεται σε όλους τους συνδυασμούς \displaystyle \left\{i_{1},i_{2},...,i_{m} \right\} των \displaystyle \left\{1,2,...,n \right\}. Ακόμη έχουμε και \displaystyle \left|\left(\bigcup_{i=1}^{n}{A_{i}} \right){'} \right|+\left|\bigcup_{i=1}^{n}{A_{i}}  \right|=\left|\Omega  \right|


Απάντηση

Επιστροφή σε “Άλγεβρα - Θεωρία Αριθμών - Συνδυαστική (Seniors) - Παλαιότερες Συζητήσεις”

Μέλη σε σύνδεση

Μέλη σε αυτήν τη Δ. Συζήτηση: Δεν υπάρχουν εγγεγραμμένα μέλη και 2 επισκέπτες