Волк и семеро козлят

[Garryncha]

Условие:
Волк поймал семерых козлят и собрался их съесть. Волк был старым пионером и сказал им: «Я запру вас в домике на ночь, а на следующее утро построю вас в колонну и надену каждому желтую или синюю пилотку. Каждый козленок будет видеть какие пилотки на козлятах, которые стоят впереди него, но не будет видеть свою собственную и тех, кто позади. Вы будете идти вперед и петь пионерские песни, а я буду спрашивать вас по очереди, начиная с последнего козлика, какого цвета у тебя пилотка. Того, кто не ответит, буду сразу съедать. Тот, кто угадает, будет помилован и отпущен. То, что будет говорить каждый козленок, будут слышать все остальные козлята. Поэтому, на мой вопрос вы должны будете отвечать монотонным голосом, без эмоций и однозначно, только «желтая» или «синяя». При попытках дать другим козликам подсказку – вся команда будет съедена целиком вместе с пилотками».

Козлики думали всю ночь и придумали такую стратегию поведения, которая позволит большинству из них выжить.

Внимание вопрос:
Что за стратегию поведения придумали козлики? Сколько козлят останутся живы? Второй вопрос – можно ли применить «козлиную» стратегию, если цветов у пилоток будет больше двух?

Ответ

Ответ:
Говорят, что эту задачу дают на собеседовании в Microsoft. Первый приходящий в голову способ решения, когда козлята с нечетными номерами говорят цвет шапочек козлят, стоящих перед ними, а козлята с четными номерами повторяют названный цвет позволит наверняка спасти только троих из всей компании, остальные четверо выживут с вероятностью 50% (если предположить цвета пилоток равно вероятными). Однако можно получить стопроцентные шансы на спасение всех козлят, кроме последнего.

Для этого поставим в соответствие желтой пилотке число 0, а синей – 1. Последний козленок складывает все числа, соответствующие пилоткам впереди стоящих, и, если число четное, говорит «желтая», если нечетное – «синяя», иными словами, говорит тот цвет, который соответствует остатку от деления суммы чисел пилоток впереди стоящих козлят на 2. Съедят его затем или нет – уже дело случая, ему самому больше ничем не помочь.

Но сам он этим спасает всех впереди стоящих. Ведь шестой козленок, услышав остаток от деления суммы чисел пилоток первых пяти козлят и своей на 2, может подсчитать остаток от деления на 2 суммы чисел пилоток первых пяти козлят, вычислить номер своей пилотки, назвать его и спастись. Аналогично и пятый – он услышал, чему равна четность суммы номеров первых шести и чему равен номер шестого, подсчитал четность суммы первых четырех и, следовательно, может вычислить свой собственный номер, т.е. цвет пилотки.

При увеличении цветов алгоритм не меняется, только шансы на спасение последнего козленка будут уменьшаться.

@темы: Головоломки и занимательные задачи

Comments

[Minority]

Хорошая задачка. Видела аналогичную, только про гномиков, и их было около сотни) Впрочем, суть от этого не меняется. Тоже человеку на собеседовании задавали, но далеко не в Microsoft. А вообще, не думаю, что ее уже действительно дают на собеседовании в Майкрософт, она довольно известная уже) Ну и, в любом случае, умение решить эту задачку не влияет на твое умение программировать, как правило...)

[Garryncha]

Minority, я не знаю, дают ли её на собеседовании в Майкрософт, просто скопировал текст целиком.:-) А где задавали задачку про гномиков, если не секрет? Я не знаю, зачем задают такие задачки на собеседованиях, и не знаю, влияет ли как-то умение их решать на умение программировать или нет.:-)

[Minority]

Garryncha
Пару лет назад одной моей ПЧ задавали, когда определяли, где она будет в армии служить (в Израиле с армией можно заключить контракт - она оплачивает твое обучение, а потом ты по специальности отрабатываешь некоторое время в одном из армейских учреждений).

Эта задача - на умение построить хитрый алгоритм с минимальными потерями в гномиках/козлятах/птичках и т.д. Алгоритмическое мышление - это хорошо, но обычно его проверяют более тривиальным способом - написанием какой-нибудь небольшой программулины. =)

[Garryncha]

Minority, как интересно, у нас в военкоматах, насколько помню, тесты попроще.:-)))

[_ТошА_]

Garryncha
У нас в военкоматах тесты блестящие просто )

[Диана Шипилова]

Да, тут было что-то похожее)) Клевая задача)

[Garryncha]

Диана Шипилова, и где-то на www.problems.ru я видел похожую.:-)

[Minority]

Garryncha
Ну так сравнили нашу армию с армией Израиля. =) К тому же, там было собеседование исключительно профессиональное, т.к. по договору отслужить надо по полученной специальности. Надо же доказать, что вложенные в тебя деньги не были невыгодным вложением =)

[Amicus Plato]

Garryncha
Здорово!

Диана Шипилова Garryncha

По-моему Фабий здесь выкладывал задачу про лампочку. И что-то смутно мне напомнило о ней, когда я эту читала... Надо поискать.

Minority
Да в качестве военкоматской задачи это жесть, конечно!

[Amicus Plato]

Нашла задачу Фабия. Она не о том... )))
Но всё равно...
www.diary.ru/~Organon/p42075557.htm

[Garryncha]

Amicus Plato, про лампочку есть ещё такая задача.
Ты находишься в команте, в которой есть 3 выключателя, к которым подключены 3 лампочки в соседней комнате. Тебе надо сначала пощёлкать выключателями, а потом перейти в соседнюю комнату и определить, каким лампочкам какие выключатели соответствуют. Вначале все выключатели выключены.

[_ТошА_]

Garryncha Мне кажется, или это просто?
Я как раз только что обжёгся о лампу

[Garryncha]

_ТошА_, это просто, я думаю, ты правильно решил.:-)

[Amicus Plato]

Я как раз только что обжёгся о лампу

Это было очень кстати)
Garryncha "определить" используя любые рецепторы?

[_ТошА_]

Amicus Plato Жестоко(

[Amicus Plato]

_ТошА_
я в хорошем смысле этого слова)))

[Garryncha]

Amicus Plato, да-да, любые.:-)

[Garryncha]

О моя повелительница, Amicus Plato, долго думал над задачей Фабия про зеков, решил наконец-то и испытал большое удовлетворение.:-)

[Amicus Plato]

Garryncha

О моя повелительница,

Какие у вас жестокие флэшмобы однако ))))))
Один другого краше )

[Garryncha]

О моя повелительница Amicus Plato, это ещё ничего, кому-то достаётся писать стишки в каждом посте, кому-то вставлять картинки с героем сериала размера не меньше, чем 300 на 300 в каждый пост и комментарий и писать: "О Зло, ты прав, он прекрасен!":-)))

[Amicus Plato]

Garryncha
(((
ужас...
Теоремы завоюют мир! ))

[Garryncha]

О моя повелительница Amicus Plato, да это прикольно.:-)))