3.5. Правила медленной игры неполным составом
В итоге мудрецы выводят для себя следующие правила медленной игры неполным составом:
1) игра неполным составом возможна только если число меченых среди уклонистов меньше, чем главный классификатор q меточного происшествия, а общее число мудрецов M больше q;
2) уклонисты должны так или иначе объявить, что они уклонисты;
3) каждый мудрец может предложить ускоряющую церемонию отказов от игры, дающую при её завершении знание хотя бы одному уклонисту, меченый он или нет;
4) если V1 и V2 – число меченых и число немеченых уклонистов, то игра первоначальным полным составом с параметрами M, q, m (число игроков, главный классификатор меточного происшествия, число меченых) может быть заменена игрой неполным составом, которая строится как игра новым полным составом (уменьшенным по сравнению с первоначальным) с параметрами M*, q*, m*, где M*=M−V1−V2, q*=q−V1, m*=m−V1;
5) состояние уклониста описывается индикатором h (h=1 – меченый, h=0 – немеченый), который либо узнаётся уклонистом по итогам ускоряющей церемонии отказов, либо вычисляется по итогам игры по формуле h=u+q−1−j , где u – номер промежутка для ВД, в котором меченые участники игры, идущей неполным составом, совершают ВД, q – главный классификатор меточного происшествия для намечавшейся игры полным составом, j – число меченых мудрецов, наблюдавшихся уклонистом в итоге этого происшествия.
3.6. Быстрая игра
Поскольку медленная игра неполным составом сводится к медленной игре новым полным составом (уменьшенным по сравнению с первоначальным), то и быстрая игра неполным составом сводится к быстрой игре новым полным составом. Исследуем возможности быстрой игры полным составом, решают мудрецы. Можно ли ускорить течение игры?
Мудрецы начинают с простого примера. Пусть возникла ситуация для медленной игры полным составом с параметрами M=7, q=1, m=5. Продиктованные внешними обстоятельствами промежутки для ВД обозначим Р1,…,Р5. Медленная игра течёт по промежуткам 1) Р1, … , 5) Р5. Каждый меченый, предположив себя немеченым, ждёт промежуток для ВД с номером m−q=4, то есть промежуток Р4. Увидев, что его меченые товарищи не совершают ВД в этом промежутке, меченый осознаёт себя меченым и совершает ВД в 5-ом промежутке, то есть в промежутке Р5. После чего немеченые понимают, что они немеченые. Промежутки с номерами 1, 2 ,3 неинформативны для мудрецов (никто не будет совершать ВД в этих промежутках). Чтобы не терять попусту время, один из мудрецов предлагает вставить в паузе перед Р1 воображаемые дополнительные промежутки В1 и В2. Все соглашаются и медленная игра превращается из несмещённой в смещённую, а со стороны это выглядит как быстрая игра (в ней раньше наступает развязка). Смещённая медленная игра течёт по промежуткам 1) В1, 2) В2, 3) Р1, 4) Р2, 5) Р3. Развязка происходит в промежутке для ВД с номером 5, только теперь это не Р5, а Р3.
Продолжая рассуждать, мудрецы приходят к следующим правилам быстрой игры полным составом:
1) быстрая игра реализуется как трансформация медленной игры, основанная на вставке по общему согласию одного или нескольких воображаемых дополнительных промежутков для ВД в паузе или паузах перед реальными промежутками;
2) при появлении дополнительных промежутков нумерация промежутков с учётом дополнительных сдвигается и медленная игра становится смещённой – она течёт по расширенному набору промежутков;
3) кроме общей нумерации в ряду с воображаемыми дополнительными промежутками реальные промежутки для ВД имеют отдельную нумерацию, в соответствии с которой события отслеживаются в быстрой игре (для наблюдателя быстрой игры воображаемых промежутков нет);
4) в число дополнительных промежутков должны попадать только неинформативные промежутки (не обязательно все), то есть промежутки, в которых никто не будет ждать ВД от товарищей;
5) мудрец, предлагающий вставку воображаемых промежутков, учитывает возможность того, что он немеченый – даже в этом случае должно быть выполнено правило 4.
Поясним рассуждения мудреца, предлагающего вставку. Пусть медленная игра полным составом имеет параметры M, q, m, где q≥1. Предположим, что кто-то из мудрецов видит q+d меченых, где d≥2. Этот кто-то не знает, меченый он или нет. Но он может стать инициатором вставки, зная, что 1) m=q+d или m=q+d+1, 2) каждый ждёт ВД от меченых не ранее чем в промежутке с номером m−q≥d. То есть для каждого мудреца промежутки для ВД с номерами 1,…,d−1 гарантированно неинформативны. На этом основании инициатор может предложить вставку от 1 до d−1 дополнительных промежутков. Сделать это он может либо в паузе перед первым реальным промежутком для ВД, либо позже. Если он пропускает паузу перед первым реальным промежутком, то в следующей паузе он может предложить вставку не более d−2 дополнительных промежутков, в следующей за следующей – не более d−3 дополнительных промежутков и так далее. То есть имеющий возможность предложить вставку может упустить эту возможность, если затянет с предложением. Предлагая вставку, мудрец глядит на ситуацию глазами товарищей и подсказку о числе меченых товарищам не даёт.