Probleem vangide ja mütsidega, mille värv tuleb kindlaks määrata
Puhkus / / December 31, 2020
Sulgemissüsteem näeb kõiki mütse, kuid oskab öelda ainult "must" või "valge", samal ajal teavitades kõiki varjatud teavet. Vangid ei tea mustade ja valgete mütside koguarvu, võimalusi on rohkem kui kaks. Kuid pariteedi mõiste puhul piirduvad need ainult kahe versiooniga: arv võib olla kas paaris või paaritu.
Probleemi lahendamise võti on järgmine: vangid nõustuvad, et esimene reageerija ütleb näiteks "must", kui ta näeb paaritu arv musti mütse ees ja "valge", kui ta näeb paarisarvu musta mütsid.
Vaatame ülaltoodud pildi näidet. Kõrgeim vang # 1 näeb ees kolme musta mütsi. Ta ütleb valjult "must". See annab kõigile teistele teavet, et ees on paaritu arv musti mütse. Esimene vang tegi vea oma mütsi värviga, kuid see on okei: kui lubatakse valesti vastata.
Vang nr 2 näeb tema ees paaritu arv musti mütse. Ta saab aru, et on valge, ja vastab õigesti. Vang # 3 näeb paarisarvulisi musti mütse ja arvab, et tal on seljas must kork, mida kaks esimest vangistajat nägid.
Vangistuses nr 4 kuuleb vastust ja saab aru, et ta peaks otsima paarisarvulisi musti mütse, sest tema selja taga oli must, kuid ta näeb ainult ühte ees ja järeldab, et tema kork on must. Vangid nr 5–9 otsivad paaritu arvu musti mütse, mida nad lihtsalt näevad, mõistes samas, et neil on valged mütsid. Pööre tuleb kümnendale vangile. Kui vang # 9 nägi paaritu arv musti mütse, tähendab see ainult ühte - vangil nr 10 on must kork.
Nii töötab see algoritm kõigi hubcapside komplektide puhul. Esimese osaleja puhul on vale vastuse tõenäosus 50%, kuid teave paaris-paaritu pariteedi kohta, mille ta annab, võimaldab ülejäänud vangidel arvata nende korki värvi.
Iga vastaja hakkab hindama eesolevate paaris- ja paaritu ülempiiri arvu. Kui tema meelest arvutatud arv ei lange kokku sellega, mida ta näeb, siis on tema kork sama värvi. Iga kord, kui sel juhul võtab järgmine reageerija arvesse, et ülejäänud tähtede paarilisus on nüüd muutunud.
See pusle on TED-Ed video tõlge.