задачка о консенсусе
Когда-то давно я слышал байку про космонавтов: воду в душ им подают под уменьшенным напором, чтобы на всех одновременно моющихся не хватало. Якобы, слаженная команда, даже не общаясь, а только крутя ручки гор-хол, может прийти к подходящему для всех решению: чтоб никто не обжигался и не замерзал.
Тогда же я придумал дискретный вариант, потом его сообща решали, а потом я решение забыл.

Колоду в 12 карт - по 4 пиковых валета, дамы и короля - раздают трем игрокам-роботам. Каждую секунду каждый игрок делает ход (все трое одновременно): либо передает одну карту соседу слева, либо бросает свои карты на стол. Команда выигрывает, если все трое одновременно бросили карты, и у каждого оказалались 4 одинаковые. Если кто-то бросил, а кто-то нет, или если кто-то бросил неодинаковые, то команда проигрывает.
Робот знает свои карты и помнит, какие карты передавались ему справа в предыдущие ходы. Что делать, он вычисляет из этого по некоторому детерминированному алгоритму, абсолютно одинаковому для всех троих.
Задача: придумать такой алгоритм, гарантирующий выигрыш. Желательно - поскорее. Смутно помню, что рекордный алгоритм у нас в любой ситуации приводил к выигрышу за не более чем 7 ходов.

Для проверки, что условия поняты правильно, задачка попроще: доказать, что если роботов 4 (а в колоду добавлены 4 пиковых туза), то эта задача неразрешима.
А вот если разрешить 4м роботам еще один способ победы: все бросили карты, и у всех одинаковый набор, - то, вроде, должна снова стать разрешимой. Не проверял, придумал только что.


Это, конечно, не про выборы папы, но навеяно.