Волк и семеро козлят
Волк поймал семерых козлят и собрался их съесть. Волк был старым пионером и сказал им: «Я запру вас в домике на ночь, а на следующее утро построю вас в колонну и надену каждому желтую или синюю пилотку. Каждый козленок будет видеть какие пилотки на козлятах, которые стоят впереди него, но не будет видеть свою собственную и тех, кто позади. Вы будете идти вперед и петь пионерские песни, а я буду спрашивать вас по очереди, начиная с последнего козлика, какого цвета у тебя пилотка. Того, кто не ответит, буду сразу съедать. Тот, кто угадает, будет помилован и отпущен. То, что будет говорить каждый козленок, будут слышать все остальные козлята. Поэтому, на мой вопрос вы должны будете отвечать монотонным голосом, без эмоций и однозначно, только «желтая» или «синяя». При попытках дать другим козликам подсказку – вся команда будет съедена целиком вместе с пилотками».
Козлики думали всю ночь и придумали такую стратегию поведения, которая позволит большинству из них выжить.
Внимание вопрос:
Что за стратегию поведения придумали козлики? Сколько козлят останутся живы? Второй вопрос – можно ли применить «козлиную» стратегию, если цветов у пилоток будет больше двух?
Ответ
Говорят, что эту задачу дают на собеседовании в Microsoft. Первый приходящий в голову способ решения, когда козлята с нечетными номерами говорят цвет шапочек козлят, стоящих перед ними, а козлята с четными номерами повторяют названный цвет позволит наверняка спасти только троих из всей компании, остальные четверо выживут с вероятностью 50% (если предположить цвета пилоток равно вероятными). Однако можно получить стопроцентные шансы на спасение всех козлят, кроме последнего.
Для этого поставим в соответствие желтой пилотке число 0, а синей – 1. Последний козленок складывает все числа, соответствующие пилоткам впереди стоящих, и, если число четное, говорит «желтая», если нечетное – «синяя», иными словами, говорит тот цвет, который соответствует остатку от деления суммы чисел пилоток впереди стоящих козлят на 2. Съедят его затем или нет – уже дело случая, ему самому больше ничем не помочь.
Но сам он этим спасает всех впереди стоящих. Ведь шестой козленок, услышав остаток от деления суммы чисел пилоток первых пяти козлят и своей на 2, может подсчитать остаток от деления на 2 суммы чисел пилоток первых пяти козлят, вычислить номер своей пилотки, назвать его и спастись. Аналогично и пятый – он услышал, чему равна четность суммы номеров первых шести и чему равен номер шестого, подсчитал четность суммы первых четырех и, следовательно, может вычислить свой собственный номер, т.е. цвет пилотки.
При увеличении цветов алгоритм не меняется, только шансы на спасение последнего козленка будут уменьшаться.
Если у вас есть интересные задачи - присылайте, указывайте также развернутый ответ.