Опять публикую задачу (на более осмысленные посты времени пока нет, ибо сессия =)
Задача довольно старая, но многие HR любят задавать её на собеседовании. Мне её рассказал человек, который проходи собеседование в IBM.
Людоед поймал 11 гномов. И предлагает им последний шанс спастись. Он даст им 1 день договориться а потом выстроет их в ряд по росту (самый высокий в конце), и на каждого наденет шапку красного или синего цвета. То есть каждый гном видет цвета шапок всех впереди стоящих гномов. Цель каждого гнома угадать какого цвета на нём шапка. Если гном угадывает, он остается в живих, иначе людоед его съедат.
За любую попытку подсказки, или изменения интонации, людоед сразу всех съест. Можно говорить только «Красный» или «Синий» ровным, чётким голосом.
Какую стратегию они должны выбрать, чтоб спаслось как можно больше гномов?
Удачи! Ответы как всегда, в комментариях через пару дней.
Есть решение на семь гномов (минимум).
Дальше думать?
То есть в любом случае спасутся семеро?
Если да то думай дальше =)
10 спасутся. Реванш ))
Молодец!
У Геры идея в ту же сторону что и у тебя(насколько я понял) , но он не развил её дальше…
Напиши полностью какая стратегия.
Последний просто говорит четность определенного цвета и готовится героически быть зохаваным. Предпоследний 10й гном видит еще 9 и располагая информацией о четности определенного цвета может определить какого цвета на нем шапка. Следующий за ним(9й), услышав 10го тоже может определить какого цвета на нем шапка… Ну и тд.
Да, абсолютно правильно!
Кстати, у последнего шанс на спасение тоже есть, так как «четность» (то есть если красных четно количество то они договорились чтобы он сказал «красный» а если не четное количество то «синий») может совпасть с его реальным цветом. Ну так в вопросе имеется ввиду стратегия при которой спасутся больше всех наверняка, то правильный ответ «10″.
Товарисчи,
на сколько я понял условие задачи – нигде не сказано сколько шапок синего и красного цвета ,а так же о том, что они должны чередоваться, по этому решения основанные на четности или не четности мне попросту не понятны, т.к. возможны ситуации когда все гномы будут в шапках одного цвета.
11 гном (самый высокий) обречен с вероятностью 50/50, но вот оставшиеся 10 гномов спасти точно удастся применяя принцип паузы
11 гном перед тем как угадать цвет своей шапки – делает (либо не делает) небольшую задержку в ответе (например 2 сек – цвет красный, 0сек – цвет синий), в зависимости от шапки своего соседа.
данное решение годится только в случае если опрос начинается с конца (с самого большого гнома)
Паузы делать нельзя!
Я тоже дошёл, только позже и по-другому, более програмистски и замудрённо.
Я разделил их по парам: либо пара одного цвета (+), либо разного (-).
Тот, кто видит всех, рассчитывает уравнение (+ + – + – = + ) и сообщает результат (допустим, красный = плюс, синий = минус).
Последняя пара видит четыре пары перед собой и решение ( + + – + ? = + ), догадывается, что у неё минус, т.е. разные цвета. Тот, что первый, называет противоположный видимому им соседу цвет, второй называет противоположный услышанному. Теперь у четвёртой пары есть результат последней (они назвали разные цвета, т.е. получился минус), первые три пары и результат, названный предположительно героически зохаваным. Они опять считают в уме ( + + – ? – = +) и называют одинаковые цвета (опять-таки, тот, что ближе к началу, говорит цвет второго, а тот за ним повторяет).
И так далее, до самой первой пары.
Только вот людоед от такой прозорливости охренеет и всё равно зохавает всех.
Поэтому предлагаю вернуться к моему апгрейженому с прошлой попытки варианту – на восемь гномов =)
Рассказать, или не важно?
С 8 гномами? Расскажи, интересно какие тут ещё есть подходы к решению задачи.
По большому счёту принцип тот же, указывается, одного ли цвета пара гномов.
Один спасает трёх: 1 – 2 – 3 – 4
Если четвёртый – красный, то для обозначения совпадающей пары первый говорит «синий». На осонвании того, сказали ли 2 и 3 тот же цвет, и что сказал перед этим первый, 4 определяет свой цвет.
Минут десять думал. И придумал.
По поводу шапки первого гнома никаких намёков, поэтому теряем его 50/50. А вот остальные могут спастись.
Обозначим красный=1, синий=0.
Первый гном говорит xor остальных десяти шапок. Тогда второй, зная xor десяти шапок и цвета девяти, способен вычислить цвет своей. После этого третий, зная xor десяти шапок и цвета девяти, также вычисляет цвет своей. И так далее.
Интересно, а такой вариант подойдёт:
Гномы стоят в шеренгу по росту, верно? Тогда людоед по очереди опрашивает гномов, например с нижнего. Если у нижнего гнома шапка синяя, то его сосед смотрит на него. Если красная – смотрит вперёд. Так они могут спасти друг друга. Предпоследний же должен будет успеть передать информацию последнему, сказав свой цвет людоеду смотря или не смотря на последнего гнома. Глупо, но вроде бы подходит.
Нет, они все стоят лицом вперед и не видят лиц друг друга, и начинаю с самого последнего, который видит всех, но его никто не видит. Так что такой трюк здесь не сработает.
Если самый высокий (с которого начинается опрос) видит всех, то он видит следующего за ним. Почему он просто не может сказать цвет шапки следующего (чтобы спасти его таким образом)? Это же вроде проще чем xor’ить
)
Допустим он стоят Красный, синий, красный, синий …
Все красные умрут так как они будут подсказывать синим их цвет, а сами не спасутся, итого умрет половина гномов.
Есть решение гораздо лучше (гуманнее =)
По условию задачи, кстати, не сказано, что синих и красных шапок будет поровну (5+6). Следовательно задача включает в себя также случаи со всеми красными (синими) шапками, т.е. все решения на чётность / нечётность не подходят.
Если множества красных и синих шапок произвольны, то
каждый гном должен говорить цвет шапки гнома, стоящего перед ним. При этом он спасает его с вероятностью 100% и имеет некоторую вероятность совпадения цвета на его шапке с названным.
Таким образом спасаются каждый второй гном (5) и некоторое число из оставшихся шести.
Да, а вариант с проверкой на чётность/нечётность ВСЕГДА оставляет в живых 10 гномов, и ещё одного с определённой вероятностью. Независимо от количества и соотношения красных и синих шапок.
Что означает фраз «чётность цвета», если цвета шапок распределены абсолютно произвольно?
Это значит что если синих(чёрных) шапок чётное количество, говорить «Синий» (например), а если иначе «Красный»
Названия цветов не важны.
Каким образом количество каждого цвета у 10 впереди стоящих гномов для 11-го будет четным или нечетным. Они будут либо всегда четными (0-10, 2-8, 4-6) либо всегда нечетными (1-9, 3-7, 5-5). Ведь свою 11-шапку он не знает!!!
Они договариваются:
Красный – количество красных шапок четное
Синий – количество красных шапок НЕ четное
Самый высокий считает и говорит, допустим красный – значит перед ним четное количество гномов с красными шапками. Он может умереть или не умереть с вероятностью 50%.
Дальше стоящий гном тоже считает сколько впереди красных шапок, если четность совпадает, то этот гном понимает что у него синяя шапка, а если четность не совпадает, то значит у него красная. Он вслух говорит цвет своей шапки, и ВСЕ впереди стоящие слышат. И так далее.
Вроде сейчас понятней объяснил?
мммда, но не обрабатывается ситуация когда у всех гномов которые перед последним в шапках одного цвета
Обрабатывается!
Если у всех одного цвета, (допустим все красные), и десятый гном (второй после самого высокого) слышит: Красный. Это значит что количество красных шапок четное, он стоит и считает, ага красных шапок передо мной 9! Значит я тоже в красной (для четности). Следующий слышит: Красный. Он думает ага, впереди меня 8 красных шапок. Самый высокий сказал, что красных четное количество, сзади меня у одного уже была красная шапка, значит это 9, ну а я десятый для четности, и тоже говорит «Красный». И т.д.
Этот способ «покрывает» все случаи!