Putnam 2002/B4

#1

Ένας ακέραιος

επιλέγεται ομοιόμορφα στην τύχη από το διάστημα [1,2002]

.

Στόχος σας είναι να βρείτε τον

μετά από περιττό αριθμό κινήσεων. Σε κάθε κίνηση μαντεύετε έναν αριθμό

από αυτό το διάστημα και πληροφορείστε αν m < n

ή

. Κάθε φορά που μαντεύετε έναν αριθμό επιβάλλεται ο αριθμός αυτός να έχει θετική πιθανότητα να είναι ο επιλεγμένος αριθμός.

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

μετά από περιττό αριθμό από μαντέματα να είναι μεγαλύτερη από 2/3

.

dement · #2

Καλό! Κατ' αρχάς παρατηρούμε ότι αν η επιλογή μας περιορίζεται σε

αριθμούς (έστω 1-4

) τότε η στρατηγική $1 \to 3$ (πρώτα το

και, σε περίπτωση αποτυχίας, το

) μας εξασφαλίζει πιθανότητα επιτυχίας 3/4

.

Θα αποδείξουμε ότι, αν έχουμε επιθυμητή στρατηγική για

αριθμούς, τότε έχουμε και για n+6

αριθμούς. Αυτό αποδεικνύει και το αποτέλεσμα, αφού $2002 \equiv 4 \mod 6$ .

Πράγματι, έστω n+6

αριθμοί (από

ως

). Αρχίζουμε με $1 \to 6$ . Αν ο αριθμός μας είναι πάνω από

(με πιθανότητα $\displaystyle \frac{n}{n+6})$ έχουμε πιθανότητα επιτυχίας p > 2/3

. Αν είναι μεταξύ

και

(με πιθανότητα $\displaystyle \frac{4}{n+6}$ ) έχουμε πιθανότητα επιτυχίας 3/4

. Αν είναι

έχουμε ήδη επιτύχει, αν είναι

έχουμε ήδη αποτύχει (με πιθανότητα $\displaystyle \frac{1}{n+6}$ για το καθένα.)

Έτσι, συνολικά η πιθανότητα επιτυχίας είναι $\displaystyle \frac{1}{n+6} + \frac{3}{n+6} + \frac{pn}{n+6} > \frac{2}{3}$ που ολοκληρώνει την απόδειξη.

#3

Δημήτρη, εγώ πήγα από το

στο

. (Δεν το δοκίμασες;)

Η πιθανότητα να κερδίσω για n=1

είναι

η οποία είναι μεγαλύτερη του 2/3

. Έστω λοιπόν πως n > 1

και $n \equiv 1 \bmod 3$ .

Επιλέγω τον

και μετά τον

. Αν είναι ο

κερδίζω, αν είναι ο

χάνω. Αν είναι ο

κερδίζω ενώ αν είναι μεγαλύτερος του

εφαρμόζω την στρατηγική επαγωγικά.

Η πιθανότητα νίκης είναι $\displaystyle{ \frac{2}{n} + \frac{p(n-3)}{n} > \frac{2}{n} + \frac{2(n-3)}{3n} = \frac{2}{3}}$

$\rule{400pt}{1pt}$

Μια απόδειξη, η οποία είμαι σίγουρος πως προέκυψε από μια παρόμοια απόδειξη με την δική μου, είναι απίστευτα πιο όμορφη.

Επιλέγουμε διαδοχικά τους αριθμούς $1,3,4,6,7,9,\ldots$ μέχρι είτε να βρούμε τον ζητούμενο αριθμό είτε να μας πουν πως είναι μικρότερος από αυτόν που είπαμε.

Αν ο αριθμός είναι ο $1,4,7,\ldots$ τότε κερδίζουμε.
Αν ο αριθμός είναι ο $3,6,9,\ldots$ τότε χάνουμε.
Αν ο αριθμός είναι ο $2,5,8,\ldots$ τότε κερδίζουμε. (Π.χ. αν είναι ο 3k+2

σε άρτια κίνηση θα πούμε το 3k+3

ενώ ήδη θα έχουμε πει τον 3k+1

. Οπότε στην επόμενη περιττή κίνηση θα πούμε τον 3k+2

.)

Άρα η πιθανότητα νίκης (με αυτήν την στρατηγική) είναι $\displaystyle{ \frac{(2/3)\times 2001 + 1}{2001+1} > \frac{2}{3} }$

Απλά

σε αυτόν που την βρήκε (είναι σε αρχείο των Kiran Kedlaya και Lenny Ng αλλά δεν ξέρω να είναι δική τους) και

που ήμουν τόσο κοντά αλλά δεν το πρόσεξα.

$\rule{400pt}{1pt}$

Μπορεί να δειχθεί ότι η βέλτιστη στρατηγική δίνει πιθανότητα νίκης $\displaystyle{ \frac{1}{n} \left \lfloor \frac{2n+1}{3}\right \rfloor}$

dement · #4

Έκατσα στην πρώτη περίπτωση που είχα βρει για n=4

και παραμέλησα τελείως την τετριμμένη για n=1

. Όπως λένε και στο σκάκι, αν βρεις μια καλή κίνηση, ψάξε για μια καλύτερη!

Putnam 2002/B4

Putnam 2002/B4

Re: Putnam 2002/B4

Re: Putnam 2002/B4

Re: Putnam 2002/B4

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