Putnam 2017/A5

Συντονιστής: Demetres

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

Putnam 2017/A5

#1

Μη αναγνωσμένη δημοσίευση από Demetres » Τετ Δεκ 06, 2017 10:55 am

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

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



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

Re: Putnam 2017/A5

#2

Μη αναγνωσμένη δημοσίευση από Demetres » Πέμ Δεκ 21, 2017 12:28 pm

Γράφω A_n,B_n,C_n για τις πιθανότητες να κερδίσουν οι A,B,C αντίστοιχα.

Παρατηρώ ότι \displaystyle  A_n = \frac{1}{n} + \frac{C_1 + \cdots + C_{n-1}}{n} αφού αν επιλέξει το 1 κερδίζει, ενώ αν επιλέξει το 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) και F_n = n(C_n-A_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. Αρκεί να δείξουμε ότι:

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

Από την συμμετρία των D,E,F αρκεί να δείξω ότι ανεξάρτητα από τις αρχικές τιμές των D_1,E_1,F_1:

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

Θα δείξω πρώτα ότι υπάρχουν αυθαίρετα μεγάλες τιμές του n ώστε D_n \geqslant 0. Έστω προς άτοπο ότι υπάρχει N \in \mathbb{N} ώστε D_n < 0 για κάθε n > N. Τότε για n > N η ακολουθία (E_n) είναι αυστηρώς φθίνουσα. Αν υπάρχει M > N ώστε E_M < 0, τότε E_n < E_M για κάθε n > M και άρα

\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 ώστε F_n < 0. Θα είναι όμως και E_n < 0 και D_n < 0, άτοπο.

Πρέπει λοιπόν E_n > 0 για κάθε n > N. (Αν έχουμε E_n = 0 για κάποιο n > N, τότε E_{n+1} < 0, άτοπο.) Τότε η (F_n) είναι αυστηρώς αύξουσα για n > M. Αν σε κάποια φάση η (F_n) γίνει μη αρνητική, τότε θα γίνει και θετική, και όπως πιο πάνω μπορούμε να δείξουμε ότι και η (D_n) θα γίνει θετική. Μπορούμε λοιπόν να υποθέσουμε ότι F_n < 0 για κάθε n > N. Τότε η (D_n) είναι αυστηρώς φθίνουσα. Άρα F_n + D_n < 0 + D_N για κάθε n > N. Άρα E_n > -D_N > 0 για κάθε n > N. Πάλι όπως πιο πάνω όμως, συμπεραίνουμε ότι η (F_n) θα γίνει σε κάποια φάση θετική.

Υπάρχει λοιπόν n > N ώστε D_n > 0. Αν F_n \leqslant 0, τότε τελειώσαμε. Αλλιώς D_{n+1} > D_n. Αν F_{n+1} \leqslant 0 πάλι τελειώσαμε. Αλλιώς D_{n+2} > D_{n+1} κ.ο.κ. Μπορούμε λοιπόν να υποθέσουμε ότι η (D_n) γίνεται θετική και αύξουσα. Τότε το ίδιο θα συμβεί και για την (E_n) χρησιμοποιώντας πάλι ότι η αρμονική σειρά αποκλίνει. Τότε όμως θα έχουμε ότι όλες οι ακολουθίες είναι θετικές, άτοπο.

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


Απάντηση

Επιστροφή σε “Διαγωνισμοί για φοιτητές”

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

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