Problēma ar ieslodzītajiem un vāciņiem, kuru krāsa ir jānosaka
Atpūta / / December 31, 2020
Aizvēršanas sistēma redz visus vāciņus, bet var pateikt tikai "melns" vai "balts", vienlaikus informējot visus par slēpto informāciju. Ieslodzītie nezina kopējo melnbalto vāciņu skaitu, ir vairāk nekā divas iespējas. Bet attiecībā uz paritātes jēdzienu tās aprobežojas ar tikai divām versijām: skaitlis var būt vai nu pāra, vai nepāra.
Problēmas risināšanas atslēga ir šāda: ieslodzītie vienojas, ka pirmais atbildētājs teiks, piemēram, "melns", ja viņš redz nepāra skaitu melnu vāciņu priekšā un "baltu", ja viņš redz pāra skaitu melnu vāciņi.
Apskatīsim piemēru no attēla iepriekš. Garākais ieslodzītais # 1 redz trīs melnus vāciņus priekšā. Viņš runā "melnā" skaļi. Tas visiem pārējiem sniedz informāciju, ka priekšā ir nepāra skaits melnu vāciņu. Pirmais ieslodzītais kļūdījās ar vāciņa krāsu, taču tas nav biedējoši: ja reiz ir atļauts atbildēt nepareizi.
Ieslodzītā # 2 viņas priekšā redz nepāra skaitu melnu vāciņu. Viņa saprot, ka ir balta, un atbild pareizi. 3. ieslodzītais redz pāra skaitu melnu vāciņu un nojauš, ka viņš valkā melnu vāciņu, ko redzēja pirmie divi gūstekņi.
Ieslodzītā Nr. 4 dzird atbildi un saprot, ka viņai jāmeklē pāra skaits melnu vāciņu, jo aiz muguras bija melns, bet viņa redz tikai vienu priekšā un secina, ka viņas vāciņš ir melns. Ieslodzītie Nr. 5-9 meklē nepāra skaitu melnu vāciņu, ko viņi redz, vienlaikus saprotot, ka viņiem ir baltas krāsas vāciņi. Pāreja pienāk pie desmitā ieslodzītā. Ja ieslodzītais Nr. 9 redzēja nepāra skaitu melnu vāciņu, tas nozīmē tikai vienu - ieslodzītajam Nr. 10 ir melns vāciņš.
Tas būtu, kā šis algoritms darbotos jebkuram hubcaps komplektam. Pirmajam dalībniekam nepareizas atbildes varbūtība ir 50%, bet informācija par pāra-nepāra paritāti, kuru viņš sniegs, ļaus pārējiem gūstekņiem uzminēt vāciņa krāsu.
Katrs respondents sāks novērtēt priekšā esošo pāra un nepāra ierobežojumu skaitu. Ja viņa prātā aprēķinātais skaitlis nesakrīt ar redzēto, tad viņa vāciņš ir vienā krāsā. Katru reizi šajā gadījumā nākamais respondents ņem vērā, ka tagad ir mainījusies atlikušo vāciņu pāra dīvainība.
Šī mīkla ir TED-Ed videoklipa tulkojums.