Сто человек стоят в ряду друг за другом лицом в одном направлении. На каждом из них красная или зелёная шляпа, которая выбиралась случайно. Каждый человек видит все шляпы людей, стоящих перед ним, но не видит своей и шляп людей, которые стоят позади него. Начиная с хвоста ряда производится опрос, во время которого каждый по очереди угадывает цвет своей шляпы. При этом участники слышат все предшествующие предположения. Стратегию действий можно обсудить всем вместе заранее. Какое максимальное число людей сможет точно определить цвет своей шляпы во время опроса и как они должны действовать? Естественно, во время опроса каждый называет только цвет и никаких других посланий передать при этом не может.
update
Первый - Илья.Ответ
99. Ошибиться может только первый отвечающий.
До того, как участники начинают озвучивать ответы, каждый человек должен посчитать красные шляпы перед ним. Если общее число нечетное, то он готовит ответ "красный", иначе - "зелёный". После этого в ожидании своей очереди каждый участник слушает ответы предыдущих отвечающих. Как только он слышит ответ "красный" он как бы переключает свой подготовленный ответ на противоположный. Когда очередь доходит до него, он отвечает сформированный на тот момент подготовленный ответ.
До того, как участники начинают озвучивать ответы, каждый человек должен посчитать красные шляпы перед ним. Если общее число нечетное, то он готовит ответ "красный", иначе - "зелёный". После этого в ожидании своей очереди каждый участник слушает ответы предыдущих отвечающих. Как только он слышит ответ "красный" он как бы переключает свой подготовленный ответ на противоположный. Когда очередь доходит до него, он отвечает сформированный на тот момент подготовленный ответ.
Обозначим красные шляпы 0, а зеленые 1.
ОтветитьУдалитьПоследний человек считает сумму видимых ему шляп и называет 0, если сумма четная, и 1 если нечетная.
Тогда следующий (видя все. кроме своей), сможет точно назвать цвет своей шляпы, и также все стоящие за ним (учитывая ответы всех предыдущих).
Ответ: 99.
а почему бы не просто назвать цвет шляпы человека перед тобой? А тот этот цвет повторит. Результат тот же?
ОтветитьУдалитьДопустим, у первого шляпа красная, у второго зеленая. Первый при такой стратегии скажет "зеленый!" и ошибется. Второй повторит за ним, и угадает. Что-то еще добавлять ему запрещено.
УдалитьА как быть третьему? Все начнется сначала... Так что может получиться, что только 50 назовут правильно цвета. Остальные - без какой-то гарантии.
определить цвет и его озвучить это не одно и тоже
ОтветитьУдалитьВ принципе верно. :)
УдалитьМожно в формулировку внести уточнение.
Кстати, аналогичный алгоритм работает и при большем числе цветов (в общем-то, при любом). Пусть всего бывают шляпы N цветов. Цветам присваиваются номера от 0 до (N-1), последний суммирует все 99 шляп, которые видит, и называет цвет, соответствующий остатку от деления суммы на N. Остальные смогут определить свои цвета однозначно.