Putnam 2002/B4

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

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

Putnam 2002/B4

#1

Μη αναγνωσμένη δημοσίευση από Demetres » Τετ Οκτ 19, 2016 10:07 pm

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

Στόχος σας είναι να βρείτε τον n μετά από περιττό αριθμό κινήσεων. Σε κάθε κίνηση μαντεύετε έναν αριθμό m από αυτό το διάστημα και πληροφορείστε αν m < n ή m=n ή m > n. Κάθε φορά που μαντεύετε έναν αριθμό επιβάλλεται ο αριθμός αυτός να έχει θετική πιθανότητα να είναι ο επιλεγμένος αριθμός.

Να δείξετε ότι υπάρχει στρατηγική ώστε η πιθανότητα να μαντέψετε σωστά τον n μετά από περιττό αριθμό από μαντέματα να είναι μεγαλύτερη από 2/3.



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

Re: Putnam 2002/B4

#2

Μη αναγνωσμένη δημοσίευση από dement » Πέμ Οκτ 20, 2016 4:14 pm

Καλό! Κατ' αρχάς παρατηρούμε ότι αν η επιλογή μας περιορίζεται σε 4 αριθμούς (έστω 1-4) τότε η στρατηγική 1 \to 3 (πρώτα το 1 και, σε περίπτωση αποτυχίας, το 3) μας εξασφαλίζει πιθανότητα επιτυχίας 3/4.

Θα αποδείξουμε ότι, αν έχουμε επιθυμητή στρατηγική για n αριθμούς, τότε έχουμε και για n+6 αριθμούς. Αυτό αποδεικνύει και το αποτέλεσμα, αφού 2002 \equiv 4 \mod 6.

Πράγματι, έστω n+6 αριθμοί (από 1 ως n+6). Αρχίζουμε με 1 \to 6. Αν ο αριθμός μας είναι πάνω από 6 (με πιθανότητα \displaystyle \frac{n}{n+6}) έχουμε πιθανότητα επιτυχίας p > 2/3. Αν είναι μεταξύ 2 και 5 (με πιθανότητα \displaystyle \frac{4}{n+6}) έχουμε πιθανότητα επιτυχίας 3/4. Αν είναι 1 έχουμε ήδη επιτύχει, αν είναι 6 έχουμε ήδη αποτύχει (με πιθανότητα \displaystyle \frac{1}{n+6} για το καθένα.)

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


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

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

Re: Putnam 2002/B4

#3

Μη αναγνωσμένη δημοσίευση από Demetres » Πέμ Οκτ 20, 2016 7:30 pm

Δημήτρη, εγώ πήγα από το n στο n+3. (Δεν το δοκίμασες;)

Η πιθανότητα να κερδίσω για n=1 είναι 1 η οποία είναι μεγαλύτερη του 2/3. Έστω λοιπόν πως n > 1 και n \equiv 1 \bmod 3.

Επιλέγω τον 1 και μετά τον 3. Αν είναι ο 1 κερδίζω, αν είναι ο 3 χάνω. Αν είναι ο 2 κερδίζω ενώ αν είναι μεγαλύτερος του 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} }

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

\rule{400pt}{1pt}

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


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

Re: Putnam 2002/B4

#4

Μη αναγνωσμένη δημοσίευση από dement » Πέμ Οκτ 20, 2016 7:35 pm

:coolspeak:

Έκατσα στην πρώτη περίπτωση που είχα βρει για n=4 και παραμέλησα τελείως την τετριμμένη για n=1. Όπως λένε και στο σκάκι, αν βρεις μια καλή κίνηση, ψάξε για μια καλύτερη!


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

Τα μαθηματικά είναι η μοναδική επιστήμη που θα μπορούσε κανείς να εξακολουθήσει να ασκεί αν κάποτε ξυπνούσε και το σύμπαν δεν υπήρχε πλέον.
Απάντηση

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

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

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