Zaporniki

Naloga

V zaporu je 23 zapornikov in 1 stražar. Stražar se odloči, da bo zapornikom omogočil odhod na prostost, pod pogojem, da pravilno rešijo uganko. Velja: stražar bo klical na zagovor vsakič po enega zapornika v poljubnem vrstnem redu, v različnih časovnih obdobjih, vsak zapornik bo prišel poljubnokrat k stražarju. Vsakemu bo postavil eno samo vprašanje: »Ali ste bili že vsi pri meni?« Odgovorijo lahko z »Da« ali »Ne«. Če odgovori z »Da«, so ob pravilnem odgovoru vsi zaporniki izpuščeni, ob napačnem odgovoru pa so vsi usmrčeni. Če zapornik odgovori z »Ne«, se nič ne zgodi. V pomoč imajo zaporniki v sobi za zasliševanje dva stikala, ki ju lahko postavijo v stanje 0 ali 1. Vsak mora premakniti eno stikalo, začetno stanje pa jim ni znano. Zaporniki imajo eno uro časa, da se med seboj dogovorijo. Kako so se zaporniki rešili? Problem posploši na n zapornikov.

Rešitev

Med zaporniki izberejo enega, ki bo števec. Ko pride zapornik prvič k stražarju premakne prvo stikalo. Nato vsi ostali zaporniki do števca premikajo le drugo stikalo, šele števec znova premakne prvo stikalo in prišteje 1 k vsoti. To počnejo toliko časa, da števec prešteje do 2 (n – 1) – takrat so gotovo vsi prišli na vrsto.