Petarde

Naloga

Imamo n avtomatov (n je končno število). Vsak avtomat lahko šteje le do m (velja: m < n). V času enega takta pride signal le od enega soseda do drugega soseda. Njihova naloga: Vsi naenkrat morajo vreči petardo. Kako jim to uspe?

Rešitev

Velja: Signali lahko potujejo z različno hitrostjo. Najprej najdi sredino vrste (tam se srečata signala z običajno hitrostjo in 3x počasnejši signal). Vrsto razpolavljamo dokler ne dobimo vsakega elementa posebej (dolžina postane 1), kar pomeni, da so vsi sinhronizirani. Če n ni 2^k - en avtomat mora odigrati vlogo dveh avtomatov.