в начало статьи
3. Решение задачи о мудрецах с удивительными ушами – теория
3.1. Основные идеи и терминология
Чтобы приступить к практике, нужно сперва выстроить теорию. Внимательные читатели могут заметить, что в поезде и у светофора были вариации одной темы. И там, и там собравшиеся в кучку мудрецы играли в Игру Меченых Мудрецов. Цель игры – выяснить, кто стал меченым, наблюдая друг за другом с минимальной сигнализацией (зеркала и подсказки игрокам типа «ты меченый» запрещены, разрешены только сигналы игроков друг другу типа «я осознал себя меченым», обсуждение вопросов организации игры и беседы на посторонние темы).
Играет обычно полный состав игроков, но в некоторых случаях может играть неполный состав. Для игры неполным составом уклонисты уведомляют остальных, что они отказываются от игры. Сделать это они могут по-разному. В том числе в форме ускоряющей церемонии (на в выбор из многих), которая позволяет хотя бы одному уклонисту при завершении церемонии понять, меченый он или нет. Игра может протекать в медленном режиме (медленная игра) и в ускоренном режиме (быстрая игра). Для быстрой игры мудрецы выбирают один из многих её вариантов.
Игра становится востребованной следующим образом. Собираются вместе M≥2 мудрецов. Неожиданно для них случается меточное происшествие – возникает ситуация, в которой любой может получить метку, а дальше воля случая. Свою метку меченый мудрец не видит, но остальным она заметна. Каждый видит каждого. Пусть m – число меченых. Оно именуется главным итогом меточного происшествия. Мудрецы получают хотя бы одно общее для всех уведомление вида m≥k, где k – классификатор меточного происшествия. Возможные значения k: 0,…,m. Наибольший из указанных классификаторов назовём главным классификатором и обозначим его q.
Главный итог происшествия известен всем мудрецам только в тривиальном случае M=q (каждый понимает, что он меченый). Нетривиальный случай M>q всегда связан с тайной. При m=q каждый меченый видит только q−1 меченых и осознаёт себя меченым, но каждый немеченый видит q меченых и не может с ходу решить, меченый он или нет. При q<m главный итог происшествия – тайна для каждого. Мудреца напрягает неизвестность. Мудрец, узнавший, что он меченый, совершает при первой возможности вынужденное действие (ВД), которое без этого знания он не совершает. Чтобы узнать свою принадлежность к меченым или немеченым, мудрецы (большие любители логических задач) по сложившейся у них традиции ставят перед собой следующую задачу.
Оторвёмся от частного случая, который произошёл, рассуждают они. Возьмём общий случай: рассмотрим все меточные происшествия, соответствующие главному классификатору q, включая случай m=q. Исключим из рассмотрения все остальные происшествия как невозможные. Выберем универсальный (охватывающий все рассматриваемые случаи) план действий, приводящий всех к пониманию, кто стал меченым, и применим этот план в нашем случае.
Подход мудрецов разумен. Как если бы им предложили найти корни квадратного уравнения x²+3x+2=0, а они сказали: выведем сперва формулу, охватывающую все уравнения вида x²+bx+c=0, а затем подставим в эту формулу b=3 и c=2.
Традиционная постановка общей задачи принимается мудрецами по умолчанию. При желании они могут договориться и отступить от традиции, изменив главный классификатор q (далее приводится пример, когда возможно и уменьшение, и увеличение q). Для увеличения q любой мудрец может озвучить перед всеми собственное уведомление, выбрав в качестве классификатора любую величину, меньшую числа меченых, которых он видит (при этом в любом случае не будет подсказки остальным о числе меченых). Для уменьшения q нужно предложить значение от 1 до q−1, если такое есть. Мудрецы обычно не предлагают друг другу обнулить главный классификатор по причине, которая станет понятна ниже. Предположим, что процедура модификации главного классификатора не случилась либо уже пройдена.
продолжение следует