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

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