Problem med fångar och mössor vars färg måste bestämmas

Stängningssystemet ser alla lock, men kan bara säga “svart” eller “vit”, samtidigt som alla informeras om den dolda informationen. Fångarna känner inte till det totala antalet svarta och vita mössor, det finns mer än två möjliga alternativ. Men de är begränsade till endast två versioner när det gäller begreppet paritet: antalet kan vara antingen jämnt eller udda.

Nyckeln till att lösa problemet är denna: fångarna är överens om att den första svararen kommer att säga till exempel "svart", om han ser ett udda antal svarta mössor framför och "vita" om han ser ett jämnt antal svarta lock.

Låt oss titta på exemplet från bilden ovan. Den högsta fången nr 1 ser tre svarta mössor framåt. Han säger "svart" högt. Detta ger alla andra informationen att det finns ett udda antal svarta mössor framåt. Den första fången gjorde ett misstag med färgen på mössan, men det här är inte skrämmande: en gång får det svara fel.

Fånge nr 2 ser ett udda antal svarta mössor framför sig. Hon inser att hon är vit och svarar korrekt. Fånge 3 ser ett jämnt antal svarta mössor och gissar att han bär en svart mössa som de två första fångarna såg.

Fång nr 4 hör svaret och inser att hon borde leta efter ett jämnt antal svarta mössor, för det var en svart bakom ryggen, men hon ser bara en framåt och drar slutsatsen att hennes mössa är svart. Fångar nr 5-9 letar efter ett udda antal svarta mössor, som de bara ser, samtidigt som de inser att de bär vita mössor. Turnen kommer till den tionde fången. Om fånge 9 såg ett udda antal svarta mössor betyder det bara en sak - fånge 10 har en svart mössa.

Så här fungerar denna algoritm för alla uppsättningar hubcaps. För den första deltagaren är sannolikheten för ett felaktigt svar 50%, men informationen om den ojämna pariteten, som han kommer att ge, gör att resten av fångarna kan gissa färgen på deras mössa.

Varje respondent kommer att börja uppskatta antalet jämna och udda lock framåt. Om det antal som beräknas i sinnet inte sammanfaller med vad han ser, är hans mössa i samma färg. Varje gång i det här fallet tar nästa responder hänsyn till att de kvarvarande mössens jämnhet nu har förändrats.

Detta pussel är en översättning av en TED-Ed-video.