[L07] The Game

Calcolo combinatorio (disposizioni, permutazioni e combinazioni) e calcolo delle probabilità.

[L07] The Game

Messaggioda Federico II » 06/12/2015, 13:31

Ebbene, o sventurato lettore, l'hai pure aperto, quindi ci hai pensato, hai perso!
Ma devi sapere che in realtà The Game non è ciò a cui hai pensato (dunque potevi risparmiarti di perdere).
In origine si chiamava Pinocchio's Guessing Game, a causa della sua presenza in una delle avventure di Pinocchio. Successivamente quando la gente iniziò a stancarsi delle storielle per bambini come Pinocchio iniziò a chiamarlo The Liar's Guessing Game (come tutti sanno, Pinocchio era un grande bugiardo) e negli ultimi tempi la tendenza comune ad abbreviare i nomi lunghi l'ha trasformato in The Game.
Ma torniamo alle origini. Pinocchio, dopo aver realizzato l'inganno tesogli dal Gatto e dalla Volpe con le monete d'oro di Mangiafoco, voleva scappare per tornare sal suo caro vecchio Geppetto, ma fu catturato dal Gatto e dalla Volpe e rinchiuso e legato in una cella attraverso le cui pareti non si potesse vedere nulla, ma solo sentire. Sia Pinocchio, sia il Gatto, sia la Volpe conoscevano il numero intero $k$ di centimetri che separava la punta del naso di Pinocchio (al momento a lunghezza naturale) da una parete della cella. Il Gatto lo scherniva dicendo: "Ti credi furbo perché vuoi scappare? Vediamo se sei così intelligente! Ti sfiderò al nostro gioco preferito!" La Volpe si intromise dicendo: "No, lo sfiderò io! Tu sei quello stupido! Se vuoi però ti lascio scegliere $n$". Il Gatto scelse un intero $n\geq1.99^k$ (lo scelse così grande per aumentare al massimo le probabilità di vittoria della Volpe), pronunciandolo a voce alta. Allora furono spiegate a Pinocchio le regole del gioco: lui avrebbe pensato a due interi $x,N$ con $1\leq x\leq N$ e avrebbe detto alla volpe $N$ con sincerità (qui Pinocchio pensava tra sé e sé che invece avrebbe mentito, ma il ricordo della voce del Grillo Parlante lo convinse a dire la verità), poi la Volpe avrebbe iniziato a fargli domande specificando un insieme $S$ di interi positivi e lui doveva rispondere immediatamente con un sì o con un no, altrimenti l'avrebbero ucciso. Dopo un numero arbitrario di domande la Volpe avrebbe detto a Pinocchio un insieme $X$ di $n$ interi positivi, se $x\in X$ avrebbe vinto e avrebbe ucciso Pinocchio, altrimenti avrebbe perso e si sarebbe rassegnata a liberarlo. Pinocchio decise che alcune volte avrebbe mentito per salvarsi la pelle (o, meglio, la corteccia) ma la Fata Turchina (che leggendo nei pensieri di Pinocchio conosceva $x$) gli apparve e gli disse che ad ogni sua bugia avrebbe allungato il suo naso di un centimetro per punirlo, e ad ogni sua risposta sincera glielo avrebbe riportato a lunghezza naturale per premiarlo. Inoltre alla fine del gioco sarebbe stato costretto a dire la verità sul fatto che $x\in X$ o meno. Pinocchio sa che il suo naso di legno non può sfondare la parete di cemento armato della cella, e quindi se si allunga troppo si spezza e lui muore dal dolore.
Dimostrare che:
a) Se $n\geq2^k$ e la Volpe è abbastanza furba Pinocchio non ha scampo.
b) Per ogni $k$ sufficientemente grande, esiste un valore di $n$ (che, ricordiamo, vale sempre almeno $1.99^k$) tale che se Pinocchio è abbastanza astuto può salvarsi.
Il responsabile della sala seminari
Avatar utente
Federico II
 
Messaggi: 449
Iscritto il: 14/05/2014, 14:53

Torna a Combinatoria e Probabilità

Chi c’è in linea

Visitano il forum: Nessuno e 1 ospite