01 02 03
3.2. Медленная Игра Меченых Мудрецов полным составом
Правила медленной игры полным составом:
1) в игре участвуют M≥2 мудрецов – все мудрецы, попавшие в меточное происшествие с главным классификатором q таким, что M>q>0;
2) цель игры – узнать без посторонней помощи, кто стал меченым, с минимальной сигнализацией между игроками (подсказки «ты меченый», «ты немеченый», «вижу столько-то меченых», «вижу столько-то немеченых» и зеркала запрещены);
3) игроки сигнализируют друг другу «я осознал себя меченым» единственным способом – совершая ВД;
4) ВД возможны только в специальных промежутках времени, чередующихся с паузами;
5) меточные происшествия с числом меченых m<q считаются невозможными, остальные – возможными;
6) мудрецы должны действовать по универсальному плану, приводящему их к цели игры при любом возможном меточном происшествии;
7) если мудрец на основании своих наблюдений за совершением или не-совершением ВД другими мудрецами может прийти к выводу, что он меченый, то он не упускает эту возможность;
8) если мудрец постигает, что он меченый, после начала очередного промежутка для ВД до начала следующего, то он совершает ВД в этом следующем промежутке;
9) игра начинается с паузы и завершается при достижении цели игры.
Величину m (главный итог происшествия) при m=q не знают немеченые мудрецы, а при m>q не знают все. Величины M, q, m – параметры игры.
Правила игры неполным составом, как и правила быстрой игры полным составом, более сложны. Мы увидим, как мудрецы шаг за шагом до них додумываются. Это увлекательное зрелище.
Но сначала изучим медленную игру полным составом. С ходу не ясно:
а) могут ли игроки соблюсти правила игры,
б) если могут, то сколькими способами.
Оказывается, что существует единственный способ соблюсти правила игры. Все ходы игроков вынуждены (определяются сложившимся раскладом на меченых и немеченых).
В случае m=q каждый меченый видит перед собой только q−1 меченых, а каждый немеченый (если таковые есть) видит q меченых. Каждый меченый, зная, что m≥q, понимает, что без него множество меченых не полно, и совершает ВД в первом промежутке. Раньше совершить ВД меченые не могут, так как нет более ранних промежутков. Позже совершить ВД меченые не могут из-за правила «не упускай возможность». Увидев ВД меченых, остальные (если они есть) спрашивают себя, что подвигло их товарищей совершить ВД. Находят причину (каждый меченый, совершивший ВД, видел перед собой только q−1 меченых) и понимают, что они немеченые.
В случае m=q+1 каждый меченый видит перед собой только q меченых, а каждый немеченый (если таковые есть) видит q+1 меченых. Каждый меченый рассуждает так. Если имеет место ситуация m=q, то все меченые совершат ВД в первом промежутке, как рассмотрено выше. Увижу это – значит я немеченый. Не увижу это – значит я меченый. Поскольку в действительности m=q+1, все меченые проводят в ожидании первый промежуток и совершают ВД во втором. Раньше совершить ВД меченые не могут из-за правила переноса ВД в следующий промежуток. Позже совершить ВД меченые не могут из-за правила «не упускай возможность». Увидев ВД меченых, остальные (если они есть) спрашивают себя, что подвигло их товарищей совершить ВД. Находят причину (каждый меченый видел перед собой только q меченых) и постигают, что они немеченые.