Putnam 2007/A3

#1

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

.

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

;

dement · #2

Παρατηρούμε ότι δεν έχει σημασία πού θα βάλουμε τα πολλαπλάσια του

, αρκεί η διάταξη να μην αρχίζει με πολλαπλάσιο του

. Αν αρχίζει με αριθμό ισότιμο με $2 \mod 3$ , τότε η διάταξη ( $\mod 3$ ), εκτός των μηδενικών, θα πρέπει να είναι 22121212121...

, που είναι αδύνατον αφού έχουμε k+1

ισοτιμίες με

και

ισοτιμίες με

.

Άρα η διάταξη εκτός των μηδενικών είναι 1121212....2

. Υπάρχουν (k+1)!

διατάξεις των

και

διατάξεις των

. Στη συνέχεια, έχουμε 2k+1

επιλογές θέσης για το πρώτο

,

επιλογές για το δεύτερο

, ... ,

επιλογές για το

-οστό.

Έτσι, συνολικά η πιθανότητα (από (3k+1)!

διατάξεις) είναι $\displaystyle \frac{(k+1)! k!}{(3k+1)!} \prod_{p=1}^k (2k+p) = \frac{k+1}{(3k+1) \binom{2k}{k}}$ .

#3

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

Την θεωρώ δύσκολη άσκηση. Αυτή η απλή παρατήρηση είναι και το κλειδί της λύσης.

Putnam 2007/A3

Putnam 2007/A3

Re: Putnam 2007/A3

Re: Putnam 2007/A3

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