Putnam 2007/A3

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

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

Putnam 2007/A3

#1

Μη αναγνωσμένη δημοσίευση από Demetres » Παρ Οκτ 28, 2016 5:00 pm

Έστω θετικός ακέραιος k.

Γράφουμε τους αριθμούς 1,2,\ldots,3k+1 με μια τυχαία σειρά στον πίνακα. Ποια είναι η πιθανότητα σε κάθε φάση αυτής της διαδικασίας το άθροισμα των αριθμών που είναι γραμμένοι στον πίνακα να μην είναι πολλαπλάσιο του 3;



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

Re: Putnam 2007/A3

#2

Μη αναγνωσμένη δημοσίευση από dement » Σάβ Οκτ 29, 2016 11:34 am

Παρατηρούμε ότι δεν έχει σημασία πού θα βάλουμε τα πολλαπλάσια του 3, αρκεί η διάταξη να μην αρχίζει με πολλαπλάσιο του 3. Αν αρχίζει με αριθμό ισότιμο με 2 \mod 3, τότε η διάταξη (\mod 3), εκτός των μηδενικών, θα πρέπει να είναι 22121212121..., που είναι αδύνατον αφού έχουμε k+1 ισοτιμίες με 1 και k ισοτιμίες με 2.

Άρα η διάταξη εκτός των μηδενικών είναι 1121212....2. Υπάρχουν (k+1)! διατάξεις των 1 και k! διατάξεις των 2. Στη συνέχεια, έχουμε 2k+1 επιλογές θέσης για το πρώτο 0, 2k+2 επιλογές για το δεύτερο 0, ... , 3k επιλογές για το k-οστό.

Έτσι, συνολικά η πιθανότητα (από (3k+1)! διατάξεις) είναι \displaystyle \frac{(k+1)! k!}{(3k+1)!} \prod_{p=1}^k (2k+p) = \frac{k+1}{(3k+1) \binom{2k}{k}}.


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

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

Re: Putnam 2007/A3

#3

Μη αναγνωσμένη δημοσίευση από Demetres » Σάβ Οκτ 29, 2016 12:13 pm

dement έγραψε:Παρατηρούμε ότι δεν έχει σημασία πού θα βάλουμε τα πολλαπλάσια του 3, αρκεί η διάταξη να μην αρχίζει με πολλαπλάσιο του 3.
Την θεωρώ δύσκολη άσκηση. Αυτή η απλή παρατήρηση είναι και το κλειδί της λύσης.


Απάντηση

Επιστροφή σε “Συνδυαστική - Προχωρημένο Επίπεδο (Seniors)”

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

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