Prigionieri

[moebius]

La mia idea era la stessa... ma il procedimento per mostrare che funziona è un po' diversa...
quante le permutazioni su 2n elementi che contengono cicli di lunghezza k>n?
Beh, ho $ 2n \choose k $ modi per scegliere chi sarà coinvolto in tale ciclo. Con questi posso ottenere (k-1)! cicli diversi ed ho (2n-k)! modi per permutare quello che rimane.
In totale quindi 2n!/k permutazioni buone e dunque la probabilità che una permutazione abbia un ciclo di lunghezza k è 1/k (poichè k>n può starcene solamente uno).
Da qui tutto uguale

Edit: Aggiunti i "2" perduti Grazie 3C273

[3C273]

Beh in effetti la tua è più semplice! Però può essere che, nei conti che hai fatto, n (e non 2n) è il numero di prigionieri?
Uffa è più bella la tua!
Comunque mi è piaciuto il problema! Soprattutto tenendo conto che senza strategia la probabilità di indovinare tutti è dell'ordine di 10^{-30}... non sono nanetti ma quasi!

[moebius]

Ho sbrodolato la notazione... uffi. Lo sapevo che ci avrei messo del mio...
Vabbè correggo

[moebius]

Se ai nanetti venisse proposta una cosa del genere troverebbero una strategia per cui si salvano nel 100% dei casi...
Oppure l'orco chiederebbe loro di salvarsi almeno una volta su 4
Comunque si... è una di quelle cose che come i nanetti ti fa pensare di aver capito male il testo o che ci sia il trucco

[moebius]

Stavamo discutendo con 3C273 di questo problema e...
qual'è secondo voi la strategia migliore che i prigionieri possono adottare se per avere salva la vita devono sbagliare tutti invece che indovinare tutti?
Nello specifico, riuscite a trovarne una che gli garantisca più dell'1% di probabilità di salvezza?

[julio14]

Esattamente la stessa. Se infatti il ciclo è lungo 100, nessuno torna al suo nome, e la probabilità che il ciclo sia lungo 100, ripetendo il ragionamento di moebius, è $ \frac{99!}{100!} $ quindi 1%.

Edit: noto ora che moebius ha scritto più dell'1%...

[moebius]

già
Il motivo per cui ho scritto più dell'1% è quello che hai spiegato magistralmente tu