Волк и семеро козлят
Волк поймал семерых козлят и собрался их съесть. Волк был старым пионером и сказал им: «Я запру вас в домике на ночь, а на следующее утро построю вас в колонну и надену каждому желтую или синюю пилотку. Каждый козленок будет видеть какие пилотки на козлятах, которые стоят впереди него, но не будет видеть свою собственную и тех, кто позади. Вы будете идти вперед и петь пионерские песни, а я буду спрашивать вас по очереди, начиная с последнего козлика, какого цвета у тебя пилотка. Того, кто не ответит, буду сразу съедать. Тот, кто угадает, будет помилован и отпущен. То, что будет говорить каждый козленок, будут слышать все остальные козлята. Поэтому, на мой вопрос вы должны будете отвечать монотонным голосом, без эмоций и однозначно, только «желтая» или «синяя». При попытках дать другим козликам подсказку – вся команда будет съедена целиком вместе с пилотками».
Козлики думали всю ночь и придумали такую стратегию поведения, которая позволит большинству из них выжить.
Внимание вопрос:
Что за стратегию поведения придумали козлики? Сколько козлят останутся живы? Второй вопрос – можно ли применить «козлиную» стратегию, если цветов у пилоток будет больше двух?
Ответ
Говорят, что эту задачу дают на собеседовании в Microsoft. Первый приходящий в голову способ решения, когда козлята с нечетными номерами говорят цвет шапочек козлят, стоящих перед ними, а козлята с четными номерами повторяют названный цвет позволит наверняка спасти только троих из всей компании, остальные четверо выживут с вероятностью 50% (если предположить цвета пилоток равно вероятными). Однако можно получить стопроцентные шансы на спасение всех козлят, кроме последнего.
Для этого поставим в соответствие желтой пилотке число 0, а синей – 1. Последний козленок складывает все числа, соответствующие пилоткам впереди стоящих, и, если число четное, говорит «желтая», если нечетное – «синяя», иными словами, говорит тот цвет, который соответствует остатку от деления суммы чисел пилоток впереди стоящих козлят на 2. Съедят его затем или нет – уже дело случая, ему самому больше ничем не помочь.
Но сам он этим спасает всех впереди стоящих. Ведь шестой козленок, услышав остаток от деления суммы чисел пилоток первых пяти козлят и своей на 2, может подсчитать остаток от деления на 2 суммы чисел пилоток первых пяти козлят, вычислить номер своей пилотки, назвать его и спастись. Аналогично и пятый – он услышал, чему равна четность суммы номеров первых шести и чему равен номер шестого, подсчитал четность суммы первых четырех и, следовательно, может вычислить свой собственный номер, т.е. цвет пилотки.
При увеличении цветов алгоритм не меняется, только шансы на спасение последнего козленка будут уменьшаться.
Если у вас есть интересные задачи - присылайте, указывайте также развернутый ответ.
Dmitry 22.12.2008
log-in.ru
40 комментариев
Александр (-17)
14.08.2013 10:50
Зачем усложнять простые вещи. Точно спасутся 6 козлят у седьмого шансы 50% (если 2 цвета). Последний называет цвет пилотки стоящего перед ним. Если у 6 и 7 цвета одинаковы, то спасутся все. Если нет, то седьмой - камикадзе. Но если бы волк был хитрее (или голоднее), то он начинал бы опрос с первого козленка, в этом случае их поголовье заметно поредело бы.
фунтик (0)
10.11.2011 11:56
да не интересно и мутно
лёха (-16)
28.07.2011 16:19
Нужно вызвать вьетнамских пионеров.
Gintoki (86)
16.01.2011 09:28
Ну что тут сказать…волк сможет съесть одного, ну может двух, все - больше он съесть не сможет такие вот дела и решать ни чего не надо:)
Щур Дарина (10)
20.12.2010 17:26
"Для этого поставим в соответствие желтой пилотке число 0, а синей – 1. Последний козленок складывает все числа, соответствующие пилоткам впереди стоящих, и, если число четное, говорит «желтая», если нечетное – «синяя», иными словами, говорит тот цвет, который соответствует остатку от деления суммы чисел пилоток впереди стоящих козлят на 2." Это как? Объясните, пожалуйста…
юляшка (0)
27.10.2010 17:22
супер.
Юля (1)
27.10.2010 17:22
юляшка: ваще клёво
МИНТоля (0)
24.09.2010 22:17
У меня проще вариант - 6выживут точно.договориться что предстоящему наступаешь на ногу если синий
Ваш лимит — 666 букв (0)
17.09.2010 06:17
Задача про поезд формулируется проще: В некоторых вагонах горит свет, в некоторых - нет. В остальном все вагоны одинаковые. В поезд запускают голышом, чтобы не было соблазну разбрасываться вещами. Можно только включать или выключать свет в вагоне.
Alexander (0)
12.01.2009 05:20
Димитрий, я согласен с вашим решением, но гарантированно спасти можно все-таки пятерых =)) Мой подход несколько иной. Я заменил цвета на математические знаки: желтый на +, и синий на -. Козленок №7 "складывает" козлят под номерами 1, 5 и 6, и произносит, в зависимости от полученного знака, цвет. Остальные дают свои ответы, отталкиваясь от полученной ранее информации. Таким образом, рискуют быть съеденными, только козлята под номерами 4 и 7.
Om (1)
28.12.2008 05:58
при увеличении цветов до семи, спасутся также 6 козлят? Интересно узнать алгоритм.
виталя (0)
11.08.2013 18:18
Om: при увеличении цветов до 7 шансы на спасение 100%,сложно незнать свой цвет зная остольные 6 впереди стоящих.
бубука (6)
26.12.2008 18:28
не правильно, он должен угадать свой цвет, не факт, что его цвет совпадет с впереди идущем, то есть на следующем козлёнке, к примеру, желтый. предыдущий говорит "желтый", а на нем на самом деле синий и т.д.
Teh Sentinel (0)
26.12.2008 15:12
Дык… для двух цветов элементарно - каждый козленок называет тот цвет, который одет на впереди идущем. В итоге гарантировано спасается 6, а если два последних (т.е. тех, с которых все начинается) в одинаковых пилотках, то все 7.
ктото (8)
13.08.2013 20:25
Teh Sentinel: ты не прав, потому что когда предпоследнему последний назвал цвет, он его назовет, то есть свой цвет, а не цвет впереди идущего.,
Димитрий (23)
24.12.2008 18:55
Отличная задачка! Жалко, только что не сказали, сколько козлят можно спасти. А то я придумал, как спасти четырёх и успокоился =)
XAVEN (-12)
24.12.2008 12:34
Дмитрий. твоя задача по моему глупейшая до нельзя.Никому в здравом уме не придет что у вандалов могут быть такие же знаки)это ужасно глупо,или хотя бы тогда надо было в условии указать.А про козлят так спасти можно 6-7 козлят,там много способов можно придумать,вопрос лишь в том,попадется первому та пилотка,которая будет соответствовать условию,которое придумали козлята))
Alexandr (0)
24.12.2008 11:38
А какой козленок отвечает первым? Тот который видит все пелотки или тот который стоит спиной ко всем?
Димитрий (23)
24.12.2008 09:17
Про поезд ROmka решил правильно. Суть была в том, что можно ходить не только в одном направлении)
R0mka (18)
24.12.2008 07:34
По поводу козлят то как вариант можно еще делать так: если впереди козленок с желтой пилоткой то отвечать на вапрос моментально, а если с синей то с задержкой в несолько секунд. Таким образом не спасется только первый ответивший наугад.
R0mka (18)
24.12.2008 02:20
И так до тех пор пока не определим количество вагонов. Но если по условиям задачи таряпку тоже надо обязательно использовать, то ей можно протереть оставшийся ботинок.
R0mka (18)
24.12.2008 02:18
Тогда(я про поезд с вандалами) делаем так: ставим в наш вагон метку мелом и идем считать вагоны в уме. Когда дойдем до вагона в котором есть метка похожая на нашу, ставим рядом с ней еще одну метку и возвращаемся обратно к первому вагону(первый определить посчитав вагоны в обратном порядке). Смотрим если рядом с нашей меткой появилась вторая то мы определили количество вагонов. Иначе возвращаемся вперед где две наших метки и продолжаем дальше считать вагоны. При встрече метки повторяем действия
99 (-3)
24.12.2008 00:06
спасти козлят можно 6-7 1 куплеты песен 1-й поют те кто видит перед собой желтый и тд
Димитрий (23)
23.12.2008 22:43
Про козлят есть способ гарантированно сохранить жизнь четырём козлятам. А повесить тряпку - это не честное решение. И тряпка и мел Вам нужны, чтобы метить вагоны, только надо ещё придумать в какой последовательности… :)
бубука (6)
23.12.2008 21:49
Димитрий, а вариант с тряпкой (привязать в вагоне)?)) и вообще тряпка и мел связаны как то с ответом, а то может быть стоит позвать проводника и спросить у него количество вагонов?), ещё про козлят: спастись могут от трёх до семи, с бОльшим количеством цветов, думаю, результат не будет имет смысла применимо к моему варианту…вот…
Димитрий (23)
23.12.2008 21:05
Свои ориентиры нарисовать невозможно! Они могут не отличаться от вандальских! А стирать цифры тоже плохо, ведь мы можем стереть и свою)
XAVEN (-12)
23.12.2008 20:34
Димитрий (6) 23.12.2008 08:26 Писать цифры мелом не выйдет, так как вандалы могли уже где-то написать вашим почерком цифру 1. Тогда вы сосчитаете вагоны неправильно. Ботинок оставлять тоже нельзя по правилам задачи, и чтобы его не спёрли вандалы. Ну это глупо.А так тряпка есть-стираем,пишем свою цифру и т.д.легко,а про козлят надо немного подумать))
бубука (6)
23.12.2008 20:09
седьмой должен назвать цвет, который одет на большинстве козлят) про поезд: тряпкой стираем надписи вандалов, мелом рисуем свои ориентиры; или привязываем тряпку в одном вагоне и идём по кругу отситывая вагоны в голове, только не нужно дополнять задачу условием, что вандалы уже привязали тряпки в нескольких вагонах на том же месте что и вы))
Димитрий (23)
23.12.2008 18:57
Вандалы были не просто талантливы, а безумно талантливые. Они могли нарисовать не только картину Репина, но ещё и точно так же, как это сделали Вы, ROmka)
Cveta (0)
23.12.2008 17:29
а можно проще (если так можно): каждый последующий козленок отвечает голосом впереди идущего, а впереди идущий просто открывает рот. съедается последний козленок, взади которого уже нет никого.
Артём (-1)
23.12.2008 16:32
Повесить ленточки через одну. Жёлтая-Синяя-Жёлтая-Синяя и вот так вот. В живых останутся 7-емеро. Если повезёт. Максимум погибнет 1 козлёнок. Если он не угадает свой цвет то последуйщий уже догадается какой у него цвет. Мне кажется можно, не взависимости от этого от того сколько цветов.
R0mka (18)
23.12.2008 08:42
Ну если вандалы сопрут ботинок, то тогда можно етим мелом нарисовать в своем вагоне картину Репина, которую вандалы точно не моглибы гденибудь нарисовать из-за отсутствия таланта , и также посчитать вагоны в уме пока не дойдешь до картины.
Димитрий (23)
23.12.2008 08:40
И это решение можно обобщить на любое количество козлят (n), по прежнему разбивая их на тройки. Тогда троек будет [n/3], где [x] - целая часть x. Тогда гарантированно спасутся 2*[n/3] козлят. :)-
Димитрий (23)
23.12.2008 08:37
Аналогично можно поступить для любого числа цветов (назовём их 1, 2, 3 и т. д.). Первый козлёнок говорит "1", если цвета у второго и третьего одинаковые, "2" - если у второго цвет на один больше, чем у третьего (для последнего цвета, первый считается большим него), "3" - если на два больше, и т.д. Козлята опять разбиваются на две тройки и седьмого-лишнего, причём двое из каждой тройки гарантированно выживают. Значит, спасутся хотя бы четыре козлёнка.
Димитрий (23)
23.12.2008 08:32
А козлят можно гарантированно спасти не более четырёх. Вот, как это делается: первый говорит "жёлтая", если у второго и третьего козлят пилотки одинакового цвета, и "синяя", если разного. Тогда второй козлёнок, видя пилотку третьего, может правильно назвать свой цвет. А третий, слыша что сказали первый и второй, знает, что у него на голове. Аналогично поступает группа четвёртый-пятый-шестой козлята. Седьмой козлёнок может назвать, что угодно.
Димитрий (23)
23.12.2008 08:26
Писать цифры мелом не выйдет, так как вандалы могли уже где-то написать вашим почерком цифру 1. Тогда вы сосчитаете вагоны неправильно. Ботинок оставлять тоже нельзя по правилам задачи, и чтобы его не спёрли вандалы.
R0mka (18)
23.12.2008 07:47
Посчитать вагоны можно не имея ни тряпки ни мела: Надо оставить свою вещь в вагоне (например ботинок) и идти по вагонам считая их в уме. Наткнувшись на ботинок можно определить последний вагон
XAVEN (-12)
23.12.2008 00:07
ну так блин для первого класса)если есть мел и человек внутри то в каждом вагоне ставить цифру и все))по моему эта интересней)
Димитрий (23)
22.12.2008 23:18
Есть, по-моему, гораздо более увлекательные задачи в таком же стиле. Вот одна из них: вы находитесь в поезде ездящем по кругу. При этом его последний вагон сцеплен с первым так, что этот стык ничем не отличается от остальных. Ни дверей наружу, ни окон в поезде нет. До вас в поезде побывали вандалы и написали что-то в некоторых вагонах мелом. Как посчитать количество вагонов в поезде, если вы находитесь внутри, а у вас есть мел и тряпка?
Димитрий (23)
22.12.2008 23:12
Я знаю, как спасти шесть козлят, а семерых всё-равно не спасти.