Olimpo Informatico

[_L_]

[Taifu]

[Salmastro]

il perfido tiranno, inteneritosi, ha deciso di dare una possibilità a Primo (siamo nel caso di numeri qualsiasi scritti sulle spalle dei condannati) e gli fa svolgere un preliminare.
Così scrive su 10 foglietti (ovviamente adesivi) 10 numeri, fra loro diversi. Li mescola, li pone a faccia in giù, poi Primo li scopre uno alla volta e sospende quando ritiene che l'ultimo numero scoperto sia il maggiore della serie. Non può prenderne uno precedente e se si scoprono tutti i foglietti il numero scelto è l'ultimo.
Se Primo indovina, quelli saranno i dieci numeri attaccati sulle spalle dei condannati, lui compreso, altrimenti il maligno despota scarta il numero indicato da Primo, attacca gli altri nove agli altri nove sodali e a Primo ne attacca un ulteriore altro (reale qualsiasi, scelto a caso), ritornando in sostanza alla vecchia situazione di partenza.
Poichè Primo è persona onesta, per cui se sbaglia nel preliminare continuerà a seguire nel prosieguo la corretta strategia, ma, se invece nel preliminare ci azzecca, l'istinto di conservazione umanamente prevarrà, qual è la probabilità che i Nove si salvino?

Salmastro

[Taifu]

[Salmastro]

...già...MG la chiamava, anche, "il gioco del Googol".
Ma come diceva Ulisse, MG ha esplorato (quasi) tutti i possibili enigmi...
Per cui chi sa la risposta, come me e come te, perchè l'ha letta, dia solo dritte!
Salmastro
P.S.: l'uso del "Googol" (un 1 seguito da 100 zeri) risolve i tuoi "problemi" di spazio, legati alla finitezza dei foglietti

[Taifu]

[Salmastro]

in che senso?

Salmastro

P.S.: in una delle due opzioni hai comunque ragione.

[Taifu]

[Salmastro]

geniale! perchè, giustamente, Secondo farebbe le veci di Primo, se questo superasse il preliminare.
Il problema, e qui è l'ulteriore malizia del despota, sta nel fatto che l'esito del preliminare è ignoto ai Nove! (prego i forumisti di considerare tale precisazione parte integrante del quesito)

Comunque, Taifu meglio di un hacker!

Salmastro

[ulisse]

[ulisse]

[ulisse]

[ulisse]

[Salmastro]

in realtà, quello da me proposto è il vecchio gioco del "googol" di GM, come sgamato da Taifu.
In quella situazione (10 foglietti compilati di nascosto, con numeri qualsiasi, fra loro diversi) Primo, con l'iter da me descritto e citato da Ulisse, "ha" una probabilità non nulla di indovinare qual è fra i 10 quello più alto, P, che, fra parentesi, al minimo è del 10%!
Precisato che Primo non può comunicare ai Nove se ha vinto o meno il preliminare (altrimenti vale l'astutissima osservazione di Taifu), se Primo ha probabilita P di salvarsi, allora i Nove avrebbero (1-P) probabilità di salvezza (almeno credo).
Da cui il mio quesito su quanto valga (1-P)
Spero di aver chiarito il mio pensiero.
Ciao
Salmastro

P.S.: in un mio precedente post avevo indicato come il Vecchio (più furbo che saggio) avesse stabilito l'identità di Primo...

[ulisse]

[Salmastro]

...ovviamente, Primo conosce la Teoria dei Giochi e segue la strategia ottimale.

Salmastro

[ulisse]

[Salmastro]

[ulisse]

Allora. Innanzi tutto ripassiamo le regole per precisare che a Primo non basta azzeccare il massimo per avere salva la vita.

A Primo vengono esibiti in sequenza dieci bigliettini recanti, ognuno un numero reale qualsiasi (se preferite intero positivo qualsiasi va bene ma non cambia nulla: la probabilità - uniforme - di beccare un numero tra infiniti numeri è comunque zero).

Quando Primo, secondo una sua strategia non determinata a priori, crede di avere di fronte il massimo tra i dieci numeri, interrompe la procedura.

Se il numero è effettivamente il massimo, i dieci bigliettini verranno appiccicati alle schiene dei condannati.

Supponiamo che questo capiti al k-esimo bigliettino.
Allora Primo conoscerà il contenuto di k degli n bigliettini (qui n=10).
Se tutti e k finiscono sulle schiene dei Nove, primo è comunque fottuto perché non sa quale numero ha sulla sua schiena.
Viceversa si salva.

Se Primo non indovina il massimo allora è fottuto comunque.

Supponiamo che la strategia adottata da Primo per l'individuazione del massimo abbia probabilità P di successo e ciò avvenga al k-esimo bigliettino estratto.

La probabilità che sulla sua schiena finisca uno dei bigliettini visionati (garantendo a Primo la vita) è dunque k/n.

Pertanto la probabilità di sopravvivenza di Primo è Pk/n e, conseguentemente, quella di sopravvivenza dei Nove è 1 - Pk/n.

Se Primo decide di scegliere un bigliettino a caso senza guardare allora P=0.1 e k=1 da cui la sua probabilità di sopravvivenza è dell'1%.

Se P sceglie la strategia ottimale allora P tende a 1/e e la sua probabilità di sopravvivenza tende a k/10e.

Se Primo adotta invece la seguente strategia suicida (di peggiori non me ne sono venuti in mente): osservare la sequenza di bigliettini e scegliere il primo numero inferiore al precedente, le probabilità di azzeccare il massimo si riducono al solo caso sfortunato (dal punto di vista di un aspirante suicida) in cui i numeri vengono esibiti in sequenza ordinata dal più piccolo al più grande.
Ciò può capitare solo in un caso su n! casi possibili (tanti quanti le permutazioni di n oggetti).
Quindi con tale strategia suicida la probabilità P di azzeccare il massimo scende a 1/10!
Poiché se il massimo viene azzeccato ciò avviene solo con l'ultimo bigliettino (k=10), Primo ha visto tutte e dieci i numeri. Quindi la sua probabilità di sopravvivenza con tale strategia suicida resta 1/10!

Se abbiamo n condannati allora possiamo dire che al crescere di n la probabilità di sopravvivenza varia tra un minimo che tende a 0 e un massimo che tende a 1/e.

Per chiudere manca solo una cosa: ai Nove non serve a nulla conoscere l'esito dei preliminari perché, in ogni caso, se Primo ha azzeccato il massimo, non collaborerà con essi. Quindi a loro non resta che considerare il numero dichiarato da Primo come utile per la loro sopravvivenza.

Altra storia se la richiesta non è di salvare i Nove tutti insieme ma di garantire il massimo numero di sopravvissuti...