Еще раз об умных гномиках

В нашей газете публиковалась задача об умных гномиках (см. [1]). Напомним ее условия.

В зале с несколькими ярусами находятся n гномиков. Их посадили в одну колонку, друг за другом таким образом, что каждый видит сидящих впереди перед ним и не видит находящихся сзади него.

Затем гномикам надели на голову шапочки — кому белую, кому черную. Ясно, что каждый гномик видит шапочки, надетые на находящихся перед ним, и не видит шапочки сидящих сзади него (и свою шапочку тоже).

После этого каждого из гномиков, начиная с сидящего последним, спросят, какого цвета на нем шапочка. Отвечать можно “белая” или “черная”. Отгадавшему цвет своей шапочки дадут рубль. Ответы каждого будут слышны всем остальным.

Снимать шапочки, поворачиваться и разговаривать гномикам запрещается.

Если каждый гномик будет отвечать наугад (вероятность угадывания — 50%), то общая сумма полученных денег составит в среднем n/2 рублей. Вместе с тем, если гномики заранее договорятся о правилах ответа, то выигрыш может быть и большим. Как им сговориться, чтобы гарантированный суммарный выигрыш был максимальным? Каким будет этот выигрыш?

При анализе этой задачи было показано, что при “умном” сговоре гарантированный суммарный выигрыш составит n – 1 рублей (!), т.е. наверняка правильно ответят все, кроме одного гномика. Он состоит в следующем.

Гномик, сидящий последним (на самом верхнем ярусе), подсчитывает число белых шапочек перед ним (назовем его S_общ) и отвечает “черная”, если это число четное, и “белая” — если нечетное. Таким образом он сообщает всем другим гномикам четность числа белых шапочек на них (четность числа S_общ).

Каждый остальной гномик, получив вопрос о цвете своей шапочки, подсчитывает число белых шапочек перед ним и складывает его с числом ответов “белая”, данных гномиками, находящимися между ним и гномиком, сидящим последним. Назовем полученную сумму S. После этого он сравнивает четность суммы S с четностью числа S_общ. Если четности S и S_общ совпадают, то гномик отвечает “черная”, если не совпадают — “белая”. Самостоятельно убедитесь, что при таких условиях отвечающий вторым сможет определить цвет своей шапочки.

Итак, при выполнении правил сговора все гномики, кроме сидящего последним, правильно назовут цвет своей шапочки. Сидящий последним (отвечающий первым) может отгадать цвет своего головного убора с вероятностью 50%, но именно от него зависит выигрыш “всей команды”.

Предлагаем читателям решить новый вариант задачи.

В зале с несколькими ярусами находятся n гномиков. Их посадили в одну колонку, друг за другом таким образом, что каждый видит сидящих впереди перед ним и не видит находящихся сзади него (см. рисунок на с. 43). Затем гномикам надели на голову шапочки — кому черную, кому — белую, кому — красную. Ясно, что каждый гномик видит шапочки, надетые на находящихся перед ним, и не видит шапочки сидящих сзади него (и свою шапочку тоже).

После этого каждого из гномиков, начиная с сидящего последним, спросят, какого цвета на нем шапочка. Отвечать можно только “белая”, “черная” или “красная”. При этом делать это с различной интонацией, с правильным или неправильным ударением, громко или не очень и т.п. — нельзя (как известно :), гномики говорят ровным голосом, монотонно и без интонации).

Отгадавшему цвет своей шапочки дадут рубль. Ответы каждого будут слышны всем остальным.

Снимать шапочки, поворачиваться и разговаривать гномикам запрещается.

Если каждый гномик будет отвечать наугад (вероятность угадывания — 33,3%), то общая сумма полученных денег составит в среднем n/3 рублей. Вместе с тем, если гномики заранее договорятся о правилах ответа, то выигрыш может быть и большим. Как им сговориться, чтобы гарантированный суммарный выигрыш был максимальным? Каким будет этот выигрыш?

 Литература

1. Умный сговор. / “В мир информатики” № 69 (“В мир информатики” № 4/2006).