Un interessante (penso abbastanza famoso) problema tratto da www.rudimathematici.com ; non conosco la soluzione, e ci ho passato davvero tante ore sopra.
Abbiamo $ n $ prigionieri, ai quali vengono distribuiti i numeri da $ 1 $ a $ n $; il guardiano fa questa dichiarazione: "Partiamo dal numero $ 2 $, che mi sta simpatico, e lo liberiamo, però resta nel cerchio. Siccome lui ha il numero $ 2 $, contiamo $ 2 $ persone in senso orario e liberiamo il prigioniero sul quale arriviamo, lasciandolo però nel cerchio; questa persona ha un numero, quindi contiamo per il suo numero(sempre in senso orario), e avanti così... Attenzione, però, se contando, ci fermiamo su una persona già liberata, fermiamo il gioco e tutti i non liberati se ne tornano in cella."
Per piccoli $ n $ si riesce facilmente a trovare una disposizione in modo che tutti i prigionieri vengano liberati (è facile dimostrare anche che per $ n $ dispari questo è impossibile). Il problema interessante è la generalizzazione a un $ 2n $ qualunque: esiste una "struttura" valida per qualsiasi $ n $ pari (partendo sempre dal prigioniero 2)?
Il mitico problema dei prigionieri in cerchio
-
pic88
- Messaggi: 741
- Iscritto il: 16 apr 2006, 11:34
- Località: La terra, il cui produr di rose, le dié piacevol nome in greche voci...
ciao a tutti.
sono nuovo del forum, di questo devo scusarmi.
ho scritto un po' di disposizioni.
n : (disposizione)
6: (2,5,3,1,6,4)
8: (2,7,5,3,1,8,6,4)
10: (2,9,7,5,3,1,10,8,6,4)
12: (2, 11,9,7,5,3,1,12,10,8,6,4)
è chiaro il procedimanto seguito.
Devo ancora provvedere a dimostrarne la validità.
spero quest'aiuto sia utile a chi sta tentando di risolvere.
[/b]
sono nuovo del forum, di questo devo scusarmi.
ho scritto un po' di disposizioni.
n : (disposizione)
6: (2,5,3,1,6,4)
8: (2,7,5,3,1,8,6,4)
10: (2,9,7,5,3,1,10,8,6,4)
12: (2, 11,9,7,5,3,1,12,10,8,6,4)
è chiaro il procedimanto seguito.
Devo ancora provvedere a dimostrarne la validità.
spero quest'aiuto sia utile a chi sta tentando di risolvere.
[/b]
Attento, Pic, ricontrolla, così come dici tu non li liberi tutti!
Ricorda che se vuoi liberarli tutti il prigioniero col numero $ n $ dev'essere l'ultimo ad essere liberato. In merito a questo, dove dovrà essere posto il prigioniero col numero $ n $ , rispetto a quello col $ 2 $ se vogliamo liberarli tutti? (c'è un solo posto buono)
Colgo di nuovo l'occasione per chiedere se qualcuno di quelli bravi bravi in combinatoria potessero darmi una mano con questo problema (ormai dispero di trovare una soluzione con le mie sole forze
). Grazie in anticipo a chiunque posti anche solo l'embrione di un'idea...
Ricorda che se vuoi liberarli tutti il prigioniero col numero $ n $ dev'essere l'ultimo ad essere liberato. In merito a questo, dove dovrà essere posto il prigioniero col numero $ n $ , rispetto a quello col $ 2 $ se vogliamo liberarli tutti? (c'è un solo posto buono)
Colgo di nuovo l'occasione per chiedere se qualcuno di quelli bravi bravi in combinatoria potessero darmi una mano con questo problema (ormai dispero di trovare una soluzione con le mie sole forze
). Grazie in anticipo a chiunque posti anche solo l'embrione di un'idea...-
pic88
- Messaggi: 741
- Iscritto il: 16 apr 2006, 11:34
- Località: La terra, il cui produr di rose, le dié piacevol nome in greche voci...
Ho controllato.
Prima di scomodare gli esperti in combinatoria, bisogna chiarire una cosa. Io credo di aver capito così:
partiamo dal n. 2 e contiamo 2 prigionieri in senso orario COMPRESO IL PRIGIONIERO N. 2!
Se non dovessimo contare il n.2, allora non esisterebbe una soluzione nemmeno per n = 4.
Ma leggevo da te che per n pari il gioco riesce sempre, per cui avevo concluso che anche il prigioniero n deve essere contato.
Pertanto, l'ultimo liberato deve essere il numero 1.
Prima di scomodare gli esperti in combinatoria, bisogna chiarire una cosa. Io credo di aver capito così:
partiamo dal n. 2 e contiamo 2 prigionieri in senso orario COMPRESO IL PRIGIONIERO N. 2!
Se non dovessimo contare il n.2, allora non esisterebbe una soluzione nemmeno per n = 4.
Ma leggevo da te che per n pari il gioco riesce sempre, per cui avevo concluso che anche il prigioniero n deve essere contato.
Pertanto, l'ultimo liberato deve essere il numero 1.
Hai ragione, mi sono scordato di omettere il caso $ n=4 $. Comunque si conta $ 2 $ a partire dal numero successvo, non dal numero stesso.pic88 ha scritto:Ho controllato.
Prima di scomodare gli esperti in combinatoria, bisogna chiarire una cosa. Io credo di aver capito così:
partiamo dal n. 2 e contiamo 2 prigionieri in senso orario COMPRESO IL PRIGIONIERO N. 2!
Se non dovessimo contare il n.2, allora non esisterebbe una soluzione nemmeno per n = 4.
Ma leggevo da te che per n pari il gioco riesce sempre, per cui avevo concluso che anche il prigioniero n deve essere contato.
Pertanto, l'ultimo liberato deve essere il numero 1.
P.S. Oggi ho trovato una soluzione al problema, ed è assolutamente elementare, anche se un po' lunga.