Колонна мегамозгов
АлгоритмыПодлые оккупанты захватили деревню мегамозгов, выстроили их друг за другом в колонну так, что каждый последующий видит всех предыдущих. На каждого мегамозга надели колпак черного или белого цвета так, что ни один мегамозг не видит свой колпак. Начиная с самого последнего (того, который видит всех, кроме себя), у каждого мегамозга по очереди спрашивают цвет его колпака. Если он ошибается, его убивают. Неизвестно, чем бы всё это закончилось, если бы мегамозги заранее не договорились, как минимизировать число убитых. Сколько мегамозгов гарантированно выживет?
1. Мегамозги могут жертвовать собой ради общего блага.
2. Распределение шляп неизвестно ни нам, ни мегамозгам. Могли надеть все черные, или 0, или любое промежуточное число.
3. Мегамозги слышат ответы друг друга.
4. Всё, что может сделать каждый мегамозг, это однократно назвать цвет своего колпака. Паузы, интонации, прикосновения и другие сигналы нельзя использовать для передачи информации.
5. Ответ должен быть справедлив для любого числа жителей.
145 комментариев