Prigionieri

[moebius]

Nel solito paese fantasioso, con le prigioni sempre in esubero, vi sono 100 condannati. Un giorno il governatore propone loro il seguente gioco per riavere la libertà.
Verranno portati uno per uno in una stanza con 100 scatole chiuse, ognuna delle quali contiene il nome di uno loro. Ogni condannato potrà aprire al più 50 di queste scatole per trovare il proprio nome. Alla sua uscita dalla stanza, le scatole saranno rimesse esattamente com'erano prima della sua entrata.
Se ognuno riuscirà nell'impresa, tutti verranno liberati. Altrimenti torneranno ai lavori forzati...
Siete in grado di suggerirgli una strategia che gli permetta di riabbracciare i propri cari, almeno nel 30% dei casi?

[julio14]

Usciti dalla stanza non possono parlare con i compagni, vero?

[moebius]

Ovviamente no...
però possono concordare, la notte prima, una strategia...
(chi sa perchè tutte le strategie si pianificano di notte )

[moebius]

Ultima nota... non sono nanetti... sono prigionieri... se fossero stati nanetti si sarebbero salvati al 100%

[julio14]

Ultimo chiarimento: i prigionieri sanno almeno se i precedenti ce l'hanno fatta, no? se no non vedo sbocchi...

[moebius]

Non ho mica capito il senso della domada....
Tutti e cento devono trovare il proprio nome...

[julio14]

In effetti ero un po' fuso quando l'ho fatta... uno si comporta in ogni caso come se quelli prima ce l'avessero fatto ma prima non avevo in corpo l'alcool di adesso, non riuscivo a ragionare

[3C273]

Ma uffi!!! Io ho una strategia che "a naso" sembrerebbe funzionare... ma non riesco a calcolare la probabilità di vittoria! Mah, ci provo ancora un po'... mi sembra di esserci quasi ma poi tutte le volte i conti diventano impossibili...

[moebius]

Non so se la risposta sia corretta... Anche perchè non so se tu sia ancora della stessa idea di questa mattina ma... Per quello che ho in mente io i calcoli non sono brutti...
Certo, una volta che ti dicono come si fa

[3C273]

Fatto!
Mi viene che la prob che ce la facciano tutti è
$ $~ 1-\sum_{k=51}^{100}{\frac{1}{k}}=0.3118...$ $

[mod_2]

Fatto!
Mi viene che la prob che ce la facciano tutti è
$ $~ 1-\sum_{k=51}^{100}{\frac{1}{k}}=0.3118...$ $

..e il ragionamento...

[moebius]

Mettilo pure... vista la sommatoria mi sa che è giusto

[3C273]

Comunque è vero, i conti erano molto semplici, il difficile è stato trovare il procedimento col quale risultavano semplici! Non so, la strategia mi è venuta in mente abbastanza in fretta (ovviamente dopo aver cercato di dimostrare che era impossibile ), ma non riuscivo a trovare una maniera sensata di fare quel conto... ma siccome alla fine la maniera veloce esiste, è un problema molto carino! Bene, bene!

[moebius]

Su su, adesso il procedimento

[3C273]

Ok, allora metto anche il ragionamento... tendo sempre ad aspettare perchè magari qualcuno vuole ancora cercare la sua soluzione... comunque...
I prigionieri si chiamano 1, 2, 3, ..., 100.
Numeriamo anche le scatole.
La strategia che propongo è:
Il prigioniero k apre per prima la k-esima scatola, trova dentro il numero j, allora apre la j-esima, eccetera, per 50 volte.
Tutti i prigionieri ce la fanno se il ciclo più lungo della permutazione ha lunghezza minore o uguale a 50 (perchè in questo caso, ogni prigioniero entro 50 passi trova il numero da cui era partito, che era quello corrispondente al suo nome).
Calcolo la probabilità che il ciclo più lungo sia lungo almeno 51.

Sia L_k l'evento "il ciclo più lungo è lungo esattamente k"

Sia N_k l'evento "i primi k numeri stanno tutti nello stesso ciclo"

Ora, P(N_k)=1/k :
basta considerare costruttivamente il ciclo... facciamo che parto dalla scatola 1, vedo cosa c'è dentro, apro quella scatola ecc, e se ritrovo la 1 continuo partendo dalla prima scatola non uscita... la prob che i primi k numeri siano tutti nello stesso ciclo equivale a chiedere che procedendo per "estrazione" in questo modo il numero 1 esca DOPO il 2, il 3, ..., il k, e cioè che sia l'ultimo tra questi. Ovviamente sono equiprobabili, e quindi 1/k.

Ora calcolo P(N_k|L_k)=1/coeff.bin(100; k)
perchè sapendo che la più lunga è lunga esattamente k, la prob che nel ciclo ci siano esattamente i primi k numeri è 1 su tutti i possibili sottoinsiemi di k elementi scelti tra 100.

Calcoliamo P(L_k|N_k)=1/coeff.bin(100; k) ...stranamente come sopra, non me l'aspettavo!
infatti voglio che i primi k numeri (di cui so già che l'1 è l'ultimo perchè stanno nello stesso ciclo) siano proprio nelle prime k scatole. Attenzione perchè questo vale solo se k>=50, perchè questo mi assicura che i primi k numeri, che so che stanno in un ciclo, stanno per forza nel ciclo più lungo.

Ora:
$ P(L_k)=\frac{P(N_k\cap L_k)}{P(N_k|L_k)}=\frac{P(L_k|N_k)\,P(N_k)}{P(N_k|L_k)} $
E quindi P(L_k)=P(N_k)=1/k

Quindi la prob che il ciclo più lungo sia lungo almeno 51 è
$ $~ \sum_{k=51}^{100}\frac{1}{k}$ $
e la probabilità che i prigionieri ce la facciano è il complementare!