Putnam 2017/A5

#1

Έχουμε

χαρτιά αριθμημένα από το

ως το

. Τρεις παίκτες, οι A,B,C

παίζουν εναλλάξ με την σειρά $A,B,C,A,\ldots$ επιλέγοντας ομοιόμορφα στην τύχη ένα χαρτί. Όταν επιλέξουν το χαρτί τους, αφαιρούν το χαρτί τους μαζί με όλα τα χαρτιά με μεγαλύτερο αριθμό. Τα υπόλοιπα χαρτιά ανακατεύονται ξανά για τον επόμενο παίκτη. ΤΟ παιγνίδι συνεχίζεται μέχρι κάποιος να επιλέξει τον αριθμό

. Αυτός είναι ο νικητής.

Να δειχθεί ότι για κάθε παίκτη, υπάρχουν αυθαίρετα μεγάλες τιμές του

για τις οποίες ο συγκεκριμένος παίκτης έχει την μεγαλύτερη πιθανότητα νίκης από τους τρεις.

#2

Γράφω

για τις πιθανότητες να κερδίσουν οι A,B,C

αντίστοιχα.

Παρατηρώ ότι $\displaystyle A_n = \frac{1}{n} + \frac{C_1 + \cdots + C_{n-1}}{n}$ αφού αν επιλέξει το

κερδίζει, ενώ αν επιλέξει το k > 1

, τότε η πιθανότητα να κερδίσει ισούται με $C_{k-1}$ .

Ομοίως έχω $\displaystyle B_n = \frac{A_1 + \cdots + A_{n-1}}{n}$ και $\displaystyle C_n = \frac{B_1 + \cdots + B_{n-1}}{n}$

Επομένως παίρνω:

$\displaystyle nA_n - (n-1)A_{n-1} = C_{n-1}$
$\displaystyle nB_n - (n-1)B_{n-1} = A_{n-1}$
$\displaystyle nC_n - (n-1)C_{n-1} = B_{n-1}$

Θέτω τώρα D_n = n(A_n-B_n), E_n = n(B_n-C_n)

και

. Παίρνω

$\displaystyle D_n - D_{n-1} = \frac{F_{n-1}}{n-1}$

$\displaystyle E_n - E_{n-1} = \frac{D_{n-1}}{n-1}$

$\displaystyle F_n - F_{n-1} = \frac{E_{n-1}}{n-1}$

Ισχύει επίσης ότι D_n+E_n+F_n = 0

. Αρκεί να δείξουμε ότι:

Υπάρχουν αυθαίρετα μεγάλες τιμές του

ώστε $D_n \geqslant 0 \geqslant F_n$ .
Υπάρχουν αυθαίρετα μεγάλες τιμές του

ώστε $E_n \geqslant 0 \geqslant D_n$ .
Υπάρχουν αυθαίρετα μεγάλες τιμές του

ώστε $F_n \geqslant 0 \geqslant E_n$ .

Από την συμμετρία των D,E,F

αρκεί να δείξω ότι ανεξάρτητα από τις αρχικές τιμές των D_1,E_1,F_1

:

Υπάρχουν αυθαίρετα μεγάλες τιμές του

ώστε $D_n \geqslant 0 \geqslant F_n$ .

Θα δείξω πρώτα ότι υπάρχουν αυθαίρετα μεγάλες τιμές του

ώστε $D_n \geqslant 0$ . Έστω προς άτοπο ότι υπάρχει $N \in \mathbb{N}$ ώστε D_n < 0

για κάθε

. Τότε για n > N

η ακολουθία (E_n)

είναι αυστηρώς φθίνουσα. Αν υπάρχει M > N

ώστε

, τότε

για κάθε

και άρα

$\displaystyle F_n = F_M + \frac{E_M}{M} + \frac{E_{M+1}}{M+1} + \cdots + \frac{E_{n-1}}{n-1} < F_M + E_M\left(\frac{1}{M} + \cdots + \frac{1}{n-1} \right)$

Επειδή η αρμονική σειρά αποκλίνει, θα υπάρχει n > M

ώστε

. Θα είναι όμως και E_n < 0

και

, άτοπο.

Πρέπει λοιπόν E_n > 0

για κάθε

. (Αν έχουμε E_n = 0

για κάποιο n > N

, τότε $E_{n+1} < 0$ , άτοπο.) Τότε η (F_n)

είναι αυστηρώς αύξουσα για n > M

. Αν σε κάποια φάση η (F_n)

γίνει μη αρνητική, τότε θα γίνει και θετική, και όπως πιο πάνω μπορούμε να δείξουμε ότι και η (D_n)

θα γίνει θετική. Μπορούμε λοιπόν να υποθέσουμε ότι F_n < 0

για κάθε

. Τότε η

είναι αυστηρώς φθίνουσα. Άρα F_n + D_n < 0 + D_N

για κάθε

. Άρα

για κάθε

. Πάλι όπως πιο πάνω όμως, συμπεραίνουμε ότι η (F_n)

θα γίνει σε κάποια φάση θετική.

Υπάρχει λοιπόν n > N

ώστε

. Αν $F_n \leqslant 0$ , τότε τελειώσαμε. Αλλιώς $D_{n+1} > D_n$ . Αν $F_{n+1} \leqslant 0$ πάλι τελειώσαμε. Αλλιώς $D_{n+2} > D_{n+1}$ κ.ο.κ. Μπορούμε λοιπόν να υποθέσουμε ότι η (D_n)

γίνεται θετική και αύξουσα. Τότε το ίδιο θα συμβεί και για την (E_n)

χρησιμοποιώντας πάλι ότι η αρμονική σειρά αποκλίνει. Τότε όμως θα έχουμε ότι όλες οι ακολουθίες είναι θετικές, άτοπο.

Οπότε το ζητούμενο αποδείχθηκε.

Putnam 2017/A5

Putnam 2017/A5

Re: Putnam 2017/A5

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