Есть много задачек про бедных гномиков, но над этой я дольше всего пыхтел, и даже думал, что доказал, что она не решаема — а она решаема.
Итак, стандартная история:
Хитрый, но справедливый троль наловил много гномиков (много — значит неизвестно сколько точно, может дюжину, а может и на много больше). Посадил их в тёмную пещеру, где ничего не видно, и надел каждому гномику по шапочке, красную или синюю, в случайном порядке. И сказал, что завтра на рассвете будет выводит гномиков по одному и ставить гуськом в ряд, так что самый последний увидит все затылки гномиков перед ним, следующий всех последующих и так далее, а самый первый будет любоваться рассветом, но никого из собратьев видеть не будет.
Затем, начиная с самого последнего, троль будет спрашивать у каждого гномика какого цвета шапочка у него на голове. Тех кто правильно угадают цвет своей шапочки — троль отпустит, а тех кто не угадает — троль съест. Каждый гномик может отвечать только «синяя» или «красная», больше ничего говорить и делать нельзя.
У гномиков есть время до утра придумать стратегию с наименьшими потерями, помогите гномикам.
Итак, стандартная история:
Хитрый, но справедливый троль наловил много гномиков (много — значит неизвестно сколько точно, может дюжину, а может и на много больше). Посадил их в тёмную пещеру, где ничего не видно, и надел каждому гномику по шапочке, красную или синюю, в случайном порядке. И сказал, что завтра на рассвете будет выводит гномиков по одному и ставить гуськом в ряд, так что самый последний увидит все затылки гномиков перед ним, следующий всех последующих и так далее, а самый первый будет любоваться рассветом, но никого из собратьев видеть не будет.
Затем, начиная с самого последнего, троль будет спрашивать у каждого гномика какого цвета шапочка у него на голове. Тех кто правильно угадают цвет своей шапочки — троль отпустит, а тех кто не угадает — троль съест. Каждый гномик может отвечать только «синяя» или «красная», больше ничего говорить и делать нельзя.
У гномиков есть время до утра придумать стратегию с наименьшими потерями, помогите гномикам.
Комментарии (17)
PapaBubaDiop
01.09.2014 10:29Автор! Для Вас резко усложню задачу — шапочки трех цветов. Для упрощения — 100 гномиков. Сколько выживет?
AndersonDunai
01.09.2014 10:29Спасение n или n-1 гномов.
Скрытый текстКаждый гном — это узел, который должен кроме того, что спасти себя, передать информацию следующим. Каким образом?
А таким, что впереди все будут слышать попытку стоящего сзади и также результат — выжил или нет.
Итак: первый гном считает разницу красных и синих шапочек, которые видит (их есть n-1 штук) и озвучивает остаток от деления сего числа на 2, кодируя его в цвет, соответствующий договоренности гномов, например, 0 — синий, 1 — красный, и либо выжывает, либо нет. НО зато следущший гном, услышав число и подсчитав количество гномов, которые есть перед ним и их цвета (а их уже n-2), сравнивает свой остаток с предыдущим и уже наверняка узнаёт, какой у него цвет. Далее все следующие гномы должны слышать, что говорят у них за спинами, и производить соответствующие вычисления в голове. Вуаля!
aapetrov3
01.09.2014 10:29Вот еще одно усложнение задачи: число гномиков счетное(то есть гномики находятся в биективном соответствии с натуральными числами), спрашивается, можно ли спасти всех, кроме конечного числа гномиков.
Ogoun
imbeat
Написал, потом подумал и понял, что был неправ.
alhimik45
Таким образом все кроме одного выживут 100% и Последний с верояностью 50 %
alhimik45
s/чёрный/синий
s/белый/красный
Ogoun
var a1 = 1 ^ 0 ^ 1 ^ 0 ^ 1 ^ 1;
var a2 = a1 ^ 0 ^ 1 ^ 0 ^ 1 ^ 1;
var a3 = a2 ^ 1 ^ 0 ^ 1 ^ 1;
var a4 = a3 ^ 0 ^ 1 ^ 1;
var a5 = a4 ^ 1 ^ 1;
var a6 = a5 ^ 1;
получим 010001, вместо ?01011.
alhimik45
Возьмём Вашу последовательность: 101011
Тогда алгоритм такой:
var a1 = 0 ^ 1 ^ 0 ^ 1 ^ 1; // 1
var a2 = a1 ^ 1 ^ 0 ^ 1 ^ 1; //0
var a3 = a1 ^ a2 ^ 0 ^ 1 ^ 1; //1
var a4 = a1 ^ a2 ^ a3 ^ 1 ^ 1; //0
var a5 = a1 ^ a2 ^ a3 ^ a4 ^ 1; //1
var a6 =a1 ^ a2 ^ a3 ^ a4 ^ a5; //1
Ogoun
Теперь понял, спасибо)
Ogoun
Данные в задаче неполные, если троль сразу съедает неправильно ответивших, это даст дополнительную информацию впередистоящим.
синий — синий = красный
синий — красный = синий
красный — синий = синий
красный — красный = красный,
В этом случае однозначно выживают двое впередистоящих. Из каждой тройки выживут точно двое, это уже 66%, и из оставшихся может выжить до половины, т.е. вполне может выжить 83% гномов.
Xazzzi
Вариант для гномов, которые не знают про операцию XOR.
PapaBubaDiop
Ладно, что 2, что 7, что 10 цветных шапок — решение не меняется, гласные тянуть не надо.