Problema su prigionieri e cappellini, il cui colore deve essere determinato
Ricreazione / / December 31, 2020
Il sistema di chiusura vede tutte le maiuscole, ma può solo dire "nero" o "bianco", informando simultaneamente tutti delle informazioni nascoste. I prigionieri non conoscono il numero totale di berretti bianchi e neri, ci sono più di due opzioni possibili. Ma sono limitati a solo due versioni quando si tratta del concetto di parità: il numero può essere pari o dispari.
La chiave per risolvere il problema è questa: i detenuti concordano sul fatto che il primo soccorritore dirà, ad esempio, "nero", se vede un numero dispari di berretti neri davanti e "bianco" se vede un numero pari di berretti neri tappi.
Diamo un'occhiata all'esempio dalla foto sopra. Il prigioniero più alto n. 1 vede tre berretti neri davanti. Dice "nero" ad alta voce. Questo dà a tutti gli altri l'informazione che c'è un numero dispari di berretti neri davanti. Il primo prigioniero ha commesso un errore con il colore del berretto, ma questo non è un grosso problema: una volta è consentito rispondere in modo errato.
Il prigioniero n. 2 vede un numero dispari di berretti neri di fronte a lei. Si rende conto di essere bianca e risponde correttamente. Il prigioniero n. 3 vede un numero pari di berretti neri e immagina di indossare un berretto nero visto dai primi due prigionieri.
La prigioniera n. 4 sente la risposta e si rende conto che dovrebbe cercare un numero pari di berretti neri, perché ce n'era uno nero dietro la schiena, ma ne vede solo uno davanti e conclude che il suo berretto è nero. I prigionieri n. 5-9 stanno cercando un numero dispari di berretti neri, che vedono solo, mentre si rendono conto di indossare berretti bianchi. Il turno arriva al decimo prigioniero. Se il prigioniero n. 9 ha visto un numero dispari di berretti neri, significa solo una cosa: il prigioniero n. 10 ha un berretto nero.
Questo è il modo in cui questo algoritmo funzionerà per qualsiasi set di coprimozzi. Per il primo partecipante, la probabilità di una risposta errata è del 50%, ma le informazioni sulla parità pari-dispari, che fornirà, consentiranno al resto dei prigionieri di indovinare il colore del loro berretto.
Ogni intervistato inizierà a stimare il numero di limiti pari e dispari in anticipo. Se il numero calcolato nella mente non coincide con ciò che vede, allora il suo berretto è dello stesso colore. Ogni volta in questo caso, il risponditore successivo tiene conto del fatto che la disparità dei limiti rimanenti è ora cambiata.
Questo puzzle è la traduzione di un video TED-Ed.