Επιτρέπεται ένα ψέμα

#1

Παίρνοντας αφορμή από το κλασικό πρόβλημα που είδαμε εδώ.

Ο παίκτης Α σκέφτεται έναν φυσικό αριθμό

από το

ως το

τον οποίο ο παίκτης Β προσπαθεί να βρει. Κάθε ερώτηση του Β πρέπει να είναι της μορφής «Ανήκει το

στο σύνολο

;» για κάποιο σύνολο

. Ο Β δικαιούται να κάνει

ερωτήσεις. Ο Α πρέπει να απαντήσει ειλικρινά σε όλες εκτός από το πολύ μία από τις ερωτήσεις του Β.

Να δείξετε ότι αν o B έχει στρατηγική για να μαντέψει σίγουρα τον αριθμό τότε $\displaystyle{N \leqslant \frac{2^n}{n+1}.}$

Petros N. · #2

Πολύ ωραία άσκηση!

Έστω ότι ο Β έχει στρατηγική νίκης κάνοντας

ερωτήσεις του τύπου: Ανήκει ο x στο S_i

για

. Σε κάθε αριθμό από το 1 έως το Ν αντιστοιχώ έναν n-ψήφιο δυαδικό αριθμό (επιτρέπονται τα 0 στην αρχή) όπου το k-οστό ψηφίο είναι 1 αν ο αριθμός ανήκει στο S_k

και το 0 αν δεν ανήκει. Στη συνέχεια με τις απαντήσεις των ερωτήσεων ο Α δίνει ένα n-ψήφιο δυαδικό αριθμό όπου το k-οστό ψηφίο του είναι 1 αν απάντησε "ναι" στην k-οστη ερώτηση και 0 αν απάντησε "όχι". Προφανώς δύο αριθμοί από το 1 ως το Ν δεν μπορούν να αντιστοιχούνται στον ίδιο n-ψήφιο αφού αν ο Α έδινε αυτόν τον n-ψήφιο ο Β δεν θα μπορούσε να αποφασίσει ποίον από τους δυο έχει σκεφτεί. Δυο αριθμοί δεν μπορούν να έχουν 1 διαφορετικό ψηφίο γιατί αν ο Α δώσει έναν από αυτούς ο Β δεν μπορεί να αποφασίσει αν έχει πει αλήθεια και είναι ο πρώτος ή 1 ψέμα στο αντίστοιχο ψηφίο και είναι ο δεύτερος. Δυο αριθμοί δεν μπορούν να έχουν ακριβώς 2 διαφορετικά ψηφία γιατί αν ο Α δώσει έναν αριθμό που συμπίπτει στα τα n-2 ίδια ψηφία τους και στα 2 διαφορετικά το ένα συμφωνεί με τον πρώτο και το άλλο με τον δεύτερο ο Β δεν θα μπορεί να ξέρει ποιόν από τους δύο επέλεξε ο Α αφού δεν γνωρίζει σε ποιο σημείο είπε ψέματα ο Α. Άρα καθε 2 n-ψήφιοι έχουν τουλάχιστον 3 διαφορετικά ψηφία.
Για $n<3 \implies N=1$ άρα ισχύει η ανισότητα. Για $3 \leq n$ πρέπει ο Β να βρεί N n-ψήφιους δυαδικούς ώστε να διαφέρουν σε περισσότερα απο 3 ψηφία.

Το προβλημα ανάγεται στο: Αν ο Β μπορεί να βρεί N n-ψήφιους δυαδικούς ώστε να διαφέρουν σε περισσότερα απο 3 ψηφία τότε θα ισχύει:
$\displaystyle{N \leqslant \frac{2^n}{n+1}.}$ . Έστω

το σύνολο των δυαδικών αυτών άρα |T|=N

Αφού κάθε 2 στο σύνολο δεν διαφέρουν σε 1 ψηφίο για κάθε δυαδικό στο σύνολο υπάρχουν n άλλοι που δεν ανήκουν σε αυτό (αλλάζοντας 1 μόνο ψηφίο του δυαδικοί παίρνουμε τους n αυτούς) και αφού 2 στο σύνολο δεν διαφέρουν σε 2 ψηφία τότε όλοι αυτοί οι n αριθμοί που αντιστοιχούν σε κάθε δυαδικό είναι διαφορετικοί μεταξύ τους (αν κάποιος αντιστοιχούσε σε 2 δυαδικούς του

τότε αυτοί οι 2 δυαδικοί θα διέφεραν το πολύ σε 2 ψηφία άτοπο). Οπότε σε κάθε στοιχείο του

αντιστοιχούν n+1

στοιχεία του $M= \left\{00...0001,00...0010,00...0011,...,10...0000 \right\}$ .
Άρα $\displaystyle{(n+1)|T| \leqslant |M|} \implies \displaystyle{N \leqslant \frac{2^n}{n+1}.}$ και τελειώσαμε.

Κάνω και 2 παρατηρήσεις:
Άν f(n)

ο μέγιστος πληθάριθμος του συνόλου

o B για $N \leq f(n)$ έχει στρατηγική νίκης γιατί από τους αντίστοιχους n-ψήφιους κατασκευάζονται τα σύνολα και για N>f(n)

δεν έχει.

Το πρόβλημα γενικεύεται περαιτέρω, δηλαδή αν ο Α επιτρέπεται να πει το πολύ

ψέματα τότε αν ο Β έχει στρατηγική νίκης: $n \leq 2k \implies N=1$ και
$n>2k \implies \displaystyle{N \leqslant \frac{2^n}{\begin{pmatrix}n \\k \end{pmatrix}+1}.}$
Η απόδειξη γίνεται με τον ίδιο τρόπο.

#3

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

Ουσιαστικά απάντησες στο ερώτημα όπου ο Β πρέπει να προαποφασίσει για το ποιες ερωτήσεις θα κάνει. Ίσως να μην ήταν ξεκάθαρο εξ αρχής αλλά ο Β κάθε φορά μπορεί να ακούσει την απάντηση στην προηγούμενη ερώτηση και αναλόγως να αποφασίσει για την επόμενη ερώτησή του. Αυτό κάνει το παιγνίδι κάπως πιο εύκολο για τον Β και για αυτόν τον λόγο κάνει και την ζωή μας πιο δύσκολη για να δείξουμε ότι δεν έχει στρατηγική νίκης στην συγκεκριμένη περίπτωση.

Υ.Γ.

(α) Σε κάποια σημεία λες «να διαφέρουν σε περισσότερα από τρία ψηφία» ενώ έπρεπε να πεις «να διαφέρουν σε περισσότερα ή ίσα από τρία ψηφία» ή «να διαφέρουν σε περισσότερα από δύο ψηφία».

(β) Το τελευταίο σου φράγμα (για το παιγνίδι όπου ο Β προαποφασίζει τις ερωτήσεις) με την ίδια ουσιαστικά απόδειξη βελτιώνεται σε $\displaystyle{\frac{2^n}{\binom{n}{0} + \cdots + \binom{n}{k}}}$ . Το ίδιο φράγμα δουλεύει και για την περίπτωση όπου ο Β αποφασίζει για την επόμενη ερώτηση αφού ακούσει την προηγούμενη απάντηση.

Eagle · #4

Πράγματι ωραία άσκηση! Μοιάζει πολύ με το IMO 2012 P3.

Έστω ότι επιτρέπεται ο Α να πει το πολύ

ψέμματα, τότε θα δείξουμε ότι αν $\displaystyle{N>\frac{2^n}{\binom{n}{0} + \cdots + \binom{n}{k}}}$ τότε ο Α έχει σίγουρα στρατιγική νίκης.

Αρχικά παρατηρούμε ότι το συγκεκριμένο παιχνίδι είναι ένα perfect information game (δεν ξέρω αν υπάρχει αυτός ο όρος στα ελληνικά) το οποιο σημαίνει ότι κάποιος από τους 2 παίχτες έχει στρατηγική νικής. Έστω ότι έχει ο Β, ο Α θα παίζει τυχαία δηλαδή η πιθανότητα να απαντήσει ναι σε μια οποιαδήποτε στιγμή είναι 1/2(Αν όντως έχει ο Β στρατηγική νίκης σίγουρα νικά τον Α που παίζει μια τυχαία στρατηγική).
Ας υποθέσουμε ότι ο Β τραβά μια γραμμή(διαγράφει) στους αριθμούς που σίγουρα δεν μπορεί να είναι ο x.

Για κάθε $\displaystyle{i \in \{ 1,2,...,n \}}$ έστω X_i=0

αν ο i έχει διαγραφεί κατα τη διάρκεια του παιχνιδίου, διαφορετικά X_i=1

. Ουσιαστικά το X_i

είναι η δείκτρια(indicator variable) για τον αριθμό i. Θέτουμε $\displaystyle{X=\sum_{i=1}^{N}{X_i}}$ το πλήθος των αριθμών που έχουν παραμείνει ανέπαφοι μετά το τέλος του παιχνιδιού. Έστω $\displaystyle{\mathbb{E}[X]}$ η προσδοκώμενη τιμή του Χ(expected value).Τώρα λόγω της γραμμικότητας της προσδωκόμενης τιμής $\displaystyle{\mathbb{E}[X]=\sum_{i=1}^{N}{\mathbb{E}[X_i]}}$ . Όμως $\displaystyle{\mathbb{E}[X_i]=\mathbb{P}(X_i=1)}$ που είναι η πιθανότητα ο αριθμός i να έχει μείνει ανέπαφος μετά τις n ερωτήσεις τύπου ναι/όχι(με πιθ. 50%) δηλαδή ίσο με $\displaystyle{\frac{\binom{n}{0} + \cdots + \binom{n}{k}}{2^n}}$ , αφού υπάρχουν 2^n

πιθανές απαντήσεις και στην ερώτηση "x=i?" ο Α μπορεί να πει το πολύ k φορές ψέμματα.

Άρα $\displaystyle{\mathbb{E}[X]=\sum_{i=1}^{N}{\mathbb{E}[X_i]}=\sum_{i=1}^{N}{\frac{\binom{n}{0} + \cdots + \binom{n}{k}}{2^n}}=N\cdot \frac{\binom{n}{0} + \cdots + \binom{n}{k}}{2^n}}$ .

Όμως εξ'υποθέσεως $\displaystyle{\mathbb{E}[X]>1}$ το οποιο σημαίνει ότι υπάρχει στρατηγική για τον Α ώστε να παραμείνουν ανέπαφοί πάνω από ένας αριθμοί μετά το πέρας του παιχνιδιού δηλαδή ο Α χάνει αφού δεν μπορεί να προσδιορίσει τον αριθμό,άτοπο καθώς ο Β έχει στρατηγική νίκης. Επομένως η αρχική μας υπόθεση είναι λανθασμένη άρα αν $\displaystyle{N>\frac{2^n}{\binom{n}{0} + \cdots + \binom{n}{k}}}$ τότε ο Α έχει σίγουρα στρατηγική νίκης.
Ενδιαφέρον νομίζω παρουσιάζει η εύρεση της στρατηγικής νίκης του Α.

Τώρα αν ο Β έχει στρατιγική νίκης θα πρέπει προφανώς $\displaystyle{N \leq \frac{2^n}{\binom{n}{0} + \cdots + \binom{n}{k}}}$ που είναι και το ζητούμενο.

Μια παρόμοια(αν όχι ίδια) άσκηση πρέπει να υπάρχει και στο βιβλίο των Alon και Spencer "The probabilistic method".

#5

Πολύ σωστά.

Eagle έγραψε: Μια παρόμοια(αν όχι ίδια) άσκηση πρέπει να υπάρχει και στο βιβλίο των Alon και Spencer "The probabilistic method".

Ουσιαστικά ίδια. Από εκεί την πήρα.

Eagle έγραψε:Μοιάζει πολύ με το IMO 2012 P3.

Πράγματι. Αν και η λύση του ΙΜΟ 2012/3 όπως την έβαλα εδώ δεν χρησιμοποιεί πιθανολογικές μεθόδους όποιος είχε δει παρόμοια πράγματα πιστεύω είχε σημαντικό πλεονέκτημα.

Πιστεύω πως και με το φετινό έκτο θέμα οι πιθανολογικές μέθοδοι γίνονται πλέον μέρος της ύλης που οι διαγωνιζόμενοι πρέπει να έχουν υπόψη.

Επιτρέπεται ένα ψέμα

Επιτρέπεται ένα ψέμα

Re: Επιτρέπεται ένα ψέμα

Re: Επιτρέπεται ένα ψέμα

Re: Επιτρέπεται ένα ψέμα

Re: Επιτρέπεται ένα ψέμα

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