I 100 cassetti

Il forum di Base5, dove è possibile postare problemi, quiz, indovinelli, rompicapo, enigmi e quant'altro riguardi la matematica ricreativa e oltre.

Moderatori: Gianfranco, Bruno

Rispondi
Lucignolo
Livello 4
Livello 4
Messaggi: 169
Iscritto il: mar apr 14, 2020 8:47 am

I 100 cassetti

Messaggio da Lucignolo »

I 100 condannati a morte

Il direttore di una prigione offre a 100 prigionieri nel braccio della morte, che sono numerati da 1 a 100, l'ultima possibilità. In una camera dispone un armadio con 100 cassetti. Il direttore mette a caso i numeri da 1 a 100 uno per ogni cassetto. I prigionieri entrano nella stanza, uno dopo l'altro. Ogni detenuto può aprire e guardare in 50 cassetti in qualsiasi ordine. I cassetti sono chiusi di nuovo in seguito. Se durante questa ricerca, ogni prigioniero trova il suo numero in uno dei cassetti, tutti i prigionieri vengono graziati. Se solo un prigioniero non trova il suo numero, tutti i prigionieri muoiono. Prima che il primo prigioniero entra nella stanza, i prigionieri possono discutere la strategia, ma non possono comunicare una volta che il primo prigioniero entra a cercare nei cassetti.

Qual è la strategia migliore dei prigionieri?

Se ogni prigioniero seleziona 50 cassetti a caso , la probabilità che un singolo prigioniero trova il suo numero è il 50%. Pertanto, la probabilità che tutti i prigionieri trovano il loro numero è il prodotto delle singole probabilità, che è ( 1/2 ) 100 ≈ 0.000 000 000 000 000 000 000 000 000 0008 , un numero irrisorio.
La situazione sembra senza speranza.

Pasquale
Livello 12
Livello 12
Messaggi: 2853
Iscritto il: mer mag 25, 2005 2:14 am

Re: I 100 cassetti

Messaggio da Pasquale »

Scusa, ma se il primo non trova il suo numero, già sono tutti condannati se ho capito bene?. C'è qualcuno che controlla cosa fanno i prigionieri quando sono dentro e che registra i risultati? Se il numero viene trovato, viene poi rimesso dentro o il cassetto resta vuoto? I prigionieri con chi non possono comunicare? Non parlano mai? Ognuno che entra, quando esce cosa può o non può fare? I prigionieri sono riconoscibili dalle singole caratteristiche fisiche o solo dai numeri che tengono appicicati addosso? Questi numeri si possono togliere o scambiare? i cassetti che contengono i numeri sono a loro volta numerati o riconoscibili in qualche modo, tipo 10 file da 10 o altro di similare?
_________________

$\text { }$ciao Immagine ciao
E' la somma che fa il totale (Totò)

Lucignolo
Livello 4
Livello 4
Messaggi: 169
Iscritto il: mar apr 14, 2020 8:47 am

Re: I 100 cassetti

Messaggio da Lucignolo »

ho messo il quesito così come l'ho trovato, mi son fatto le tue stesse domande

(per fare delle prove possiamo diminuire il numero dei condannati a 10)

ma in effetti se il primo sbaglia son tutti morti...

però il quesito chiede se si possa migliorare la percentuale di vincita con una strategia di comune accordo...

ma qua non c'è neppure una lampadina da accedere o spegnere!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

ahahahahhahahahhahaha

delfo52
Livello 9
Livello 9
Messaggi: 1556
Iscritto il: mer mag 25, 2005 4:19 pm
Località: bologna

Re: I 100 cassetti

Messaggio da delfo52 »

la prima piccola informazione aggiuntiva che mi viene in mente è questa.
Se i ragazzi hanno stabilito che il primo aprirà i primi 50 cassetti, e il primo sopravvive (con tutti gli altri 99), a questo punto, essi sanno che il numero 1 era (e tuttora è) in uno dei primi 50 cassetti. Il secondo, aprendo i cassetti da 51 a 100, avrà 50/99 di probabilità. Sempre meglio che niente...
Enrico

Pasquale
Livello 12
Livello 12
Messaggi: 2853
Iscritto il: mer mag 25, 2005 2:14 am

Re: I 100 cassetti

Messaggio da Pasquale »

Praticamente trattasi di un quesito che punta più al calcolo di una probabilità X di salvezza (da perfezionare per il meglio), piutttosto che all'individuazione di una strategia che assicuri certamente la salvezza per tutti, come nell'altro quesito. La vedo difficile. Magari occorrerebbe un curva rappresentativa del fenomeno, di cui calcolare il massimo.
_________________

$\text { }$ciao Immagine ciao
E' la somma che fa il totale (Totò)

Lucignolo
Livello 4
Livello 4
Messaggi: 169
Iscritto il: mar apr 14, 2020 8:47 am

Re: I 100 cassetti

Messaggio da Lucignolo »

dando per scontato che è impossibile che tutti trovino il numero e pensando solo a migliorare la percentuale irrisoria di fare il 100%

direi che vedo bene una strategia che faccia aprire tutti i cassetti in misura uguale

ovvero che si eviti che tutti aprano solo i primi 50 cassetti... (che darebbe garantito il 50% di ritrovamenti)

tipo il primo li apre da 1 a 50, il secondo da 2 a 51 e cosi via il 90 fino a 100 e poi da 1 a 40, si avrebbe che ogni cassetto sarà stato aperto lo stesso numero di volte.

oppure i prigionieri con numero pari aprono solo i cassetti con numeri pari e viceversa i prigionieri con numero dispari ;D

forse la percentuale del 50% non cambia, ma almeno ho avuto la soddisfazione di aprirli sicuramente tutti :)

franco
Livello 9
Livello 9
Messaggi: 1438
Iscritto il: mar dic 12, 2006 12:57 pm
Località: Bèrghem (Sardegna)

Re: I 100 cassetti

Messaggio da franco »

mah ...
Forse si può far qualcosa di buono se consentiamo che i ragazzi possano spostare i numeri fra i cassetti aperti (lasciandone sempre uno per cassetto, altrimenti diventa troppo facile).

Il primo ragazzo apre i primi 50 cassetti.
Se non trova il numero 1 (50%) chiaramente finisce tutto; in caso contrario mette il numero 1 nel cassetto 1 (scambiandolo con il numero presente in tale cassetto) e fa la stessa cosa con tutti i numeri minori di 50 che ha trovato. In particolare, se ha trovato il numero 2 lo mette nel cassetto 2.

Il secondo ragazzo apre il cassetto 2.
Se trova il 2 apre poi i cassetti dal 51 al 99 mettendo al posto giusto tutti i numeri che trova.
Se nel cassetto 2 c'era un numero diverso, apre prima il cassetto corrispondente a quel numero (sicuramente > 50) e poi altri 48 (sempre >50).
In ogni caso fra i primi 50 aperti dal primo ragazzo e gli altri 49 aperti da lui, è quasi sicuro che trovi il numero 2.

A questo punto è probabile che circa metà dei cassetti abbiano il numero giusto al loro interno.

I ragazzi dal terzo al cinquantesimo fanno allo stesso modo del secondo; quelli dal qinquantunesimo in poi invece se non trovano il proprio numero al primo colpo vanno a provare con 49 cassetti della prima cinquantina.

Non escludo ulteriori ottimizzazioni.

ciao

Franco
Franco

ENGINEER
noun. (en-juh-neer)
someone who does precision guesswork based on unreliable data provided by those of questionable knowledge.
See also wizard, magician

Lucignolo
Livello 4
Livello 4
Messaggi: 169
Iscritto il: mar apr 14, 2020 8:47 am

Re: I 100 cassetti

Messaggio da Lucignolo »

ho trovato una soluzione su questa pagina che pare tradotta letteralmente dall'inglese https://it.qwe.wiki/wiki/100_prisoners_problem

qua si parla di 30% di salvezza per tutti, ma la soluzione proposta e testata a me non da nessun miglioramento...

boh....

franco
Livello 9
Livello 9
Messaggi: 1438
Iscritto il: mar dic 12, 2006 12:57 pm
Località: Bèrghem (Sardegna)

Re: I 100 cassetti

Messaggio da franco »

Lucignolo ha scritto:
lun mag 04, 2020 11:24 am
ho trovato una soluzione su questa pagina che pare tradotta letteralmente dall'inglese https://it.qwe.wiki/wiki/100_prisoners_problem

qua si parla di 30% di salvezza per tutti, ma la soluzione proposta e testata a me non da nessun miglioramento...

boh....
Non voglio leggere la soluzione; non adesso per lo meno.
Vorrei però sapere, visto che l'hai letta, se è consentito spostare i numeri da un cassetto all'altro.
Così vedo di provare a calcolare la probabilità di salvezza della mia ipotesi e magari provo ad affinarla.
Franco

ENGINEER
noun. (en-juh-neer)
someone who does precision guesswork based on unreliable data provided by those of questionable knowledge.
See also wizard, magician

Lucignolo
Livello 4
Livello 4
Messaggi: 169
Iscritto il: mar apr 14, 2020 8:47 am

Re: I 100 cassetti

Messaggio da Lucignolo »

No nessuno spostamento nella soluzione

tutto resta nei cassetti, nessun trucco di alcun tipo, pura matematica...

ma ho provato non mi sfagiola...

Admin
Amministratore del sito
Amministratore del sito
Messaggi: 869
Iscritto il: mer apr 20, 2005 3:47 pm
Località: Benevento

Re: I 100 cassetti

Messaggio da Admin »

Ciao Lucignolo, e grazie per aver postato questo quesito.
Mi è piaciuto molto.
Ad intuito mi è parso un quiz poco noto, ma di quelli che poi finiscono in "letteratura" per cui non ho resistito e ho cercato la soluzione (si trova facilmente).
Bello davvero.
Penso sia un super candidato per la collezione di Base5 :)
franco ha scritto:
lun mag 04, 2020 1:38 pm
Non voglio leggere la soluzione; non adesso per lo meno.
Vorrei però sapere, visto che l'hai letta, se è consentito spostare i numeri da un cassetto all'altro.
Così vedo di provare a calcolare la probabilità di salvezza della mia ipotesi e magari provo ad affinarla.
Ciao Franco, ti confermo che non si possono spostare i biglietti da un cassetto all'altro.

Saluti
Admin
Pietro Vitelli (Amministratore del Forum)
"Un matematico è una macchina che converte caffè in teoremi" Paul Erdös
www.pvitelli.net

federico.agostini.76
Nuovo utente
Nuovo utente
Messaggi: 1
Iscritto il: lun nov 20, 2023 10:52 pm

Re: I 100 cassetti

Messaggio da federico.agostini.76 »

Dopo giorni e giorni di riflessione sono finalmente giunto alla mia soluzione personale, con relativa dimostrazione e calcolo che vi descrivo qui di seguito.
La dimostrazione è un po' lunga, ma a mio parere più comprensibile di quella che ho poi letto sul sito linkato, che richiede una conoscenza matematica di base non alla mia portata
La cosa rassicurante è che il risultato a cui sono arrivato in modo autonomo, grazie al foglio di calcolo che ho realizzato, coincide con quello ottenibile attraverso le formule descritte nel link.

Soluzione:
I cassetti vengono numerati da 1 a 100
Ogni prigioniero apre per primo il cassetto corrispondente al proprio numero.
Se non trova il proprio numero, apre come secondo il cassetto corrispondente al numero contenuto nel primo cassetto.
Se non trova ancora il proprio numero, apre come terzo il cassetto corrispondente al numero contenuto nel secondo cassetto.
E così via, sperando di trovare il proprio numero (chiudendo il "loop") entro i 50 tentativi.
Utilizzando questa strategia, i prigionieri vincono se i numeri sono stati disposti in modo da avere "loop" composti da 50 o meno numeri.
Basta un "loop" composto da 51 o più numeri ed il gioco fallisce.
Si può dimostrare, con un metodo di calcolo iterativo, che la probabilità di successo dei prigionieri è pari a circa il 31%.

Dimostrazione e calcolo:
Procediamo per gradi, ipotizzando un numero via via crescente di giocatori. Il numero di giocatori ovviamente coinciderà con quello dei cassetti totali. La condizione che dovrà sempre essere rispettata sarà sempre quella riguardante il numero (massimo) di cassetti apribili: n.50, indipendentemente dal numero di giocatori.
Se i giocatori fossero 50, il gioco avrebbe probabilità di riuscita pari al 100%, ovviamente.
Se i giocatori fossero 51, il primo giocatore (seguendo la strategia) avrebbe 1/51 di probabilità di trovare il proprio numero ogni volta che apre un cassetto. Difatti il metodo seguito corrisponde ad un ordine casuale di apertura.
Quindi avrà 50/51 di probabilità di chiudere il loop entro 50 tentativi (il che significa che tutti i loop saranno composti da 50 o meno numeri, ossia che il gioco sarà vinto), ed 1/51 di probabilità di chiudere il loop al 51esimo tentativo (il che significa che esiste un loop composto da 51 o più numeri, ossia che il gioco sarà perso).
Se i giocatori fossero 52, il primo giocatore (seguendo la strategia) avrebbe 1/52 di probabilità di trovare il proprio numero ogni volta che apre un cassetto.
Quindi avrà 50/52 di probabilità di chiudere il loop entro 50 tentativi, ed 2/52 di probabilità di chiudere il loop al 51esimo tentativo o oltre (il che significa che esiste un loop composto da 51 o più numeri, ossia che il gioco sarà perso).
Se chiude il loop entro 50 tentativi, esistono due casi:
- Lo chiude al primo tentativo ("loop" di lunghezza 1), e allora i 51 giocatori rimanenti ricadranno nella situazione identica al caso già analizzato in precedenza.
- Oppure lo chiude ad un tentativo fra il secondo ed il 50esimo, il che significa che tutti i loop rimanenti saranno composti da 50 o meno numeri, ossia che il gioco sarà vinto
Se i giocatori fossero 53, il primo giocatore (seguendo la strategia) avrebbe 1/53 di probabilità di trovare il proprio numero ogni volta che apre un cassetto.
Quindi avrà 50/53 di probabilità di chiudere il loop entro 50 tentativi, ed 3/52 di probabilità di chiudere il loop al 51esimo tentativo o oltre (il che significa che esiste un loop composto da 51 o più numeri, ossia che il gioco sarà perso).
Se chiude il loop entro 50 tentativi, esistono tre casi:
- Lo chiude al primo tentativo ("loop" di lunghezza 1), e allora i 52 giocatori rimanenti ricadranno nella situazione identica al caso già analizzato in precedenza.
- Lo chiude al secondo tentativo ("loop" di lunghezza 2), e allora anche l'altro giocatore del suo loop sarà automaticamente "salvo", ed i 51 giocatori rimanenti ricadranno nella situazione identica al caso già analizzato in precedenza.
- Oppure lo chiude ad un tentativo fra il terzo ed il 50esimo, il che significa che tutti i loop rimanenti saranno composti da 50 o meno numeri, ossia che il gioco sarà vinto
Se i giocatori fossero 54, si ripeterebbe iterativamente il ragionamento del caso precedente.
Così via fino ad arrivare al caso presentato, con 100 cassetti e 100 giocatori
I calcolo iterativo, effettuato con foglio excel, conduce ad una probabilità di riuscita del gioco dei 100 cassetti pari a:
31,183%

newdelfo
Nuovo utente
Nuovo utente
Messaggi: 11
Iscritto il: mer lug 19, 2023 9:25 am

Re: I 100 cassetti

Messaggio da newdelfo »

Il testo non mi risulta univoco. Ok per la salvezza generale se tutti trovano il proprio numero. ok la morte generale se solo uno manca. "solo uno"? Io avevo capito che se a mancare il ritrovamento erano 2 o 3, o anche tutti, a salvarsi erano comunque quelli che avevano trovato. non c'è scritto, ma mi pare coerente con lo spirito. In tal caso, per evitare che sia uno solo il mancante, la strategia che consiglio è lasciare a tutti libertà di aprire a caso, ma evitare i cassetti 99 e 100 (o altri due concordati). Così, sicuramente 2 sbagliano, ma degli altri 98, il 50 percento si salva

Rispondi