Задача. 100 Шляп

[suslad 1]

Террористы взяли 100 заложников и хотят сыграть с ними в такую игру:

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

Он может ответить только "белый" или "черный".

(Каждый заложник не может видеть свою шапку, соответсвенно не видит какого она цвета.)

Если он отвечает правильно, то остается жить, если нет - террористы его убивают.

При этом другие заложники могут слышать его ответ, но не знают убили его или нет.

У заложников есть какое то время заранее договориться о стратегии ответов.

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

[GOLF_stream 293]

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

Как должен отвечать КАЖДЫЙ, чтобы ОН остался жив? Тогда останутся живы ВСЕ.

А вообще, я бы тебе надел такую шляпу...

[suslad 1]

Че то я не догоняю. Это ответ или попытка замять эту задачу.

[nut888 3]

Террористы взяли 100 заложников и хотят сыграть с ними в такую игру:

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

Он может ответить только "белый" или "черный".

(Каждый заложник не может видеть свою шапку, соответсвенно не видит какого она цвета.)

Если он отвечает правильно, то остается жить, если нет - террористы его убивают.

При этом другие заложники могут слышать его ответ, но не знают убили его или нет.

У заложников есть какое то время заранее договориться о стратегии ответов.

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

Вот несколько ключевых понятий к данной задаче

Дилемма заключенного

Принцип парето

Задача о выборе стратегии не однозначна и не так проста

<noindex>Статья</noindex>

Очевидно что заранее договорившись начиная с последнего через одного каждый заложник будет называть

цвет шапки впередистоящего сообщая ему об этом гарантирует со 100% вероятностью что 50 человек останутся в живых

Остальные как повезет но наиболее вероятно что выживет 75 человек

[suslad 1]

Скажем так, должны выжить 99 человек плюс 1 50/50 %.

Я смотрю слово "террористы" очень режет слух. Можно перефразировать заменив террористов на учителя, заложников на детей, а наказание, или вернее спасение, на конфеты. Суть от этого не поменяется. Это чисто математическая задача. Не более того.

[nut888 3]

Скажем так, должны выжить 99 человек плюс 1 50/50 %.

Чтобы выполнялось это условие нужно в ответ вложить дополнительную информацию

Он может ответить только "белый" или "черный".

кроме того что указано в условии задачи

Если в сообщении можно передать более одного бита информации то это возможно

Очевидно что в худшем положении оказывается последний

(с кого начинается цепочка ответов)

[suslad 1]

Очевидно что в худшем положении оказывается последний

(с кого начинается цепочка ответов)

Вот именно он и есть тот который

1 50/50 %

[Whitehor 0]

Скажем так, должны выжить 99 человек плюс 1 50/50 %...

Ни хрена 99 не выживут. Даже если последний назовет шляпу впереди стоящего, то следующий назвав свой цвет, не назовет цвет впереди стоящего. Сл-но, у следующего тоже лотерея, называет цвет впереди стоящего и т.д.

[suslad 1]

Почему надо обязательно называть цвет впереди стоящего? Может стоит договориться КАК поступить первому чтобы следующий мог определить цвет своей шляпы?

[Форумный боец 1]

Скажем так, должны выжить 99 человек плюс 1 50/50 %.

задача формулируется именно так.

исходя из этого условие

но не знают убили его или нет

лишнее.

ps: а решения я не знаю :)

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

Изменено 10 августа 2007 пользователем Форумный боец

[suslad 1]

Верной дорОгой идете товарисчи!

Осталось совсем чуть-чуть...

[nut888 3]

Кстати в условии задачи не уточнено

Видит ли отвечающий только цвет шапки впередистоящего или он видит шапки всех впередистоящих

Я предыдущее решение указал с условием видимости только одного

Если видимы все то решение может быть таким

Последний называет цвет шапки впередистоящего

А далее по цепочке цвет своей шапки можно вычислить

(если известно начальное количество белых и черных) зная цвета всех впередистоящих

и предполагая что с предпоследнего никто не ошибся (возможно кроме последнего)

[suslad 1]

Кстати в условии задачи не уточнено

Видит ли отвечающий только цвет шапки впередистоящего или он видит шапки всех впередистоящих

Я предыдущее решение указал с условием видимости только одного

Еще раз напомню содержание

Заложников выводят в коридор и ставят друг за другом (т.е. каждый заложник <b>может видеть только впереди стоящих</b>), потом каждому заложнику надевают шапку (черную или белую) и начинают спрашивать заложников с конца очереди какого цвета на нем шапка.

Если видимы все то решение может быть таким

Последний называет цвет шапки впередистоящего

А далее по цепочке цвет своей шапки можно вычислить (если известно начальное количество белых и черных) зная цвета всех впередистоящих и предполагая что с предпоследнего никто не ошибся (возможно кроме последнего)

Сколько черных и белых -- неизвестно. Да оно и не надо :)

[Форумный боец 1]

Сколько черных и белых -- неизвестно

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

[Kus 36]

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

[Whitehor 0]

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

А если шапок 50/50 и одевают их случайным образом... В условии не сказано, что шапки чередуются...

И если все будут называть один цвет, то погибнуть может уйма народу...

Хотя не более 50...

[Kus 36]

Ну, не томите... Какой ответ-то?

[suslad 1]

Сначала подсказка.

Цвет определяет человек, который начинает говорить, т.е. последний в колонне, т.к. ему видно всех впередистоящих и он может прикинуть, какой цвет преобладает

Это практически решение, осталось лишь добавить КАК они договорились. Т.е. последний, назвав какой-то цвет согласно их договоренности, даст возможность 99-му точно ОПРЕДЕЛИТЬ какого цвета на нем шляпа.

[redflow 0]

Скажем так, должны выжить 99 человек плюс 1 50/50 %.

Я смотрю слово "террористы" очень режет слух. Можно перефразировать заменив террористов на учителя, заложников на детей, а наказание, или вернее спасение, на конфеты. Суть от этого не поменяется. Это чисто математическая задача. Не более того.

Меняется, и очень. Неужели ты с самого начала не догадывался о некорректности задачи и о возможности изменить условия. Жестокое описание вызывает отвращение, а говорящий-антипатию.

[suslad 1]

Меняется, и очень. Неужели ты с самого начала не догадывался о некорректности задачи и о возможности изменить условия. Жестокое описание вызывает отвращение, а говорящий-антипатию.

Специально для redflow: Как детям договориться, чтобы конфету получило наибольшее количество детей.