OliForum Matematico

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

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!

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

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

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?

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%...

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