Задача о 10 узниках

[YuG]

Есть такая классная задача (на логику).
Кто любит поломать голову пару часов, то это то, что надо (реклама на канале ОРТ <!--emo&:)--><!--endemo-->. Лично мне потребовалось три дня и куча бумаги для ее решения...

Итак, задача.
В тюрьме сидят 10 узников. Вечером им говорят, что их всех завтра на рассвете поведут казнить. Выстроят в шеренгу так, что каждый будет видеть впереди идущих, и, естественно, не сможет видеть тех, кто сзади (т.е. друг за другом). Каждому наденут на голову шапочку, но он не будет знать какого она цвета (каждая шапочка может быть одного из четырех цветов, например, белая, желтая, синяя или зеленая). А затем у каждого из них по очереди, начиная с последнего идущего (который видит всех узников, но которого не видит ни один узник), спросят: «Какого цвета шапочка у тебя на голове?». В случае, если человек угадывает цвет, его оставляют в живых, иначе – нет.
У них есть ночь на размышление, чтоб договориться, придумать систему ответов, чтоб количество выживших было МАКСИМАЛЬНЫМ.

Дополнительные факты: Цвет каждой шапочки произволен (т.е. один из четырех), даже допустимо, что все шапочки одного цвета.

Хреновый вариант решения:
- Они будут говорить наугад (вероятность выживания 25%)

Ну, лады, периодически, если кто-нибудь заинтересуется, я буду подкидывать подсказки... Хотя может кто-нибудь и сразу решит...
Есть вопросы - задавайте...
Удачи!

[Dutchman]

То есть, последний будет знать, какого цвета шапки остальных ?
Смотри ЛС.

[Bastion]

не очень понятно из условия:
1. Будут ли остальные слышать ответы предыдущего?
2. Сколько слов может сказать отвечающий на вопрос?
Если остальные слышат отвечающего, и сказать можно хотябы два слова, то только у последнему придется угадывать, и не важно ни кол-во цветов ни кол-во узников...
Или уточни условия, или я не понимаю о чем ты три дня думал...

[YuG]

2Dutchman:
каждый видит все шапки у впередистоящих.

2Bastion:
Ответы предыдущих слышат все
Отвечающий на вопрос может сказать только ОДНО слово (цвет своей шапки)

задача на самом деле очень сложная (я так считаю), но решить можно.

ПОДСКАЗКА: 100% результата нет, т.к. самый последний узник не распологает никакой информацией ---> вероятность его выживания 25% (как повезет)

[YuG]

НОВАЯ ПОДСКАЗКА:
Последний чувак одновременно подсказывает всем

[Флинт]

Эх, знаю я решение подобной задачи, но в моём варианте было только два цвета шапок - чёрный и белый. Ну и узников было 100, а не 10 С ходу переделать решение для 4-х цветов не удалось, надо подумать... Пока ни ответа, ни решения двухцветовой задачи писать тут не буду, а то неинтересно...

Добавлено:
Что-то я ступил, очевидный способ переноса решения есть. Пришёл в голову через 10 секунд после того, как я запостил сообщение

[TankMan]

... ну хоть намек дайте!!!! ... чего-то я вообще выхода не нахожу действенного

[Bes]

То есть у узников есть только два источника информации:
1) Цвета шапок у тех, кто идет перед ними.
2) Те ответы, которые дают идущие позади.
???
А всякие там жесты, подглядывания и прочее не прокатывают?
И вообще каков механизм всей этой церемонии? Как только кто-то из узников дал ответ, его сразу казнят/отводят в сторону в зависимости от правильности ответа? Или каждый остается в шеренге, пока все не ответят?
А также узнают ли узники сразу о правильности своего ответа или ответа идущих сзади?

[Bastion]

2YuG
Прошу подсказок больше не давать.
Интересней обсудить решение с теми кто его не знает.

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

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

Но, к сожалению, схем гораздо больше 4, потому при каких-то раскладках, придется рисковать и 9 и 8 узникам. К сожалению сейчас нет времени плотно занятся прописыванием схем.
Но, повторюсь, знающие ответ: НЕ НАДО БОЛЬШЕ ПОДСКАЗОК!
Кому нетерпится - в ЛС

[YuG]

2Bastion:
Хорошо, подсказок больше не будет.
<!--QuoteBegin--></div><table border='0' align='center' width='95%' cellpadding='3' cellspacing='1'><tr><td>Цитата </td></tr><tr><td id='QUOTE'><!--QuoteEBegin-->
Кому нетерпится - в ЛС
<!--QuoteEnd--></td></tr></table><div class='postcolor'><!--QuoteEEnd-->
Согласен

2Bes:
<!--QuoteBegin--></div><table border='0' align='center' width='95%' cellpadding='3' cellspacing='1'><tr><td>Цитата </td></tr><tr><td id='QUOTE'><!--QuoteEBegin-->
То есть у узников есть только два источника информации:
1) Цвета шапок у тех, кто идет перед ними.
2) Те ответы, которые дают идущие позади.
А всякие там жесты, подглядывания и прочее не прокатывают?
<!--QuoteEnd--></td></tr></table><div class='postcolor'><!--QuoteEEnd-->
АБСОЛЮТНО верно.

<!--QuoteBegin--></div><table border='0' align='center' width='95%' cellpadding='3' cellspacing='1'><tr><td>Цитата </td></tr><tr><td id='QUOTE'><!--QuoteEBegin-->
Как только кто-то из узников дал ответ, его сразу казнят/отводят в сторону в зависимости от правильности ответа? Или каждый остается в шеренге, пока все не ответят?
А также узнают ли узники сразу о правильности своего ответа или ответа идущих сзади?
<!--QuoteEnd--></td></tr></table><div class='postcolor'><!--QuoteEEnd-->
Не имеет значения.
Естесственно, если кто-то в цепочке ошибается, то все остальные тоже ошибаются - хотя это уже подсказка (извини, Bastion, так получилось)

Всех с Наступающим!!!

[YuG]

2Флинт
<!--QuoteBegin--></div><table border='0' align='center' width='95%' cellpadding='3' cellspacing='1'><tr><td>Цитата </td></tr><tr><td id='QUOTE'><!--QuoteEBegin-->
Эх, знаю я решение подобной задачи, но в моём варианте было только два цвета шапок - чёрный и белый. Ну и узников было 100, а не 10
<!--QuoteEnd--></td></tr></table><div class='postcolor'><!--QuoteEEnd-->
кстати, может запостишь эту задачу?

[Slater]

Джентельмены, если все свои предположения кидать исключительно в ЛС, то задачка так и останется нерешенной. По-моему так!

[YuG]

Кстати, предположения можно кидать и сюда - я буду отвечать.
В ЛС предлагается кидать только варианты решения (или мольбы выслать ответ ))
И еще, у этой задачи есть ЧЁТКОЕ решение, поэтому не тратьте время на всякие глупые идеи.
Все, я на пару дней ушел праздновать...

[Флинт]

2YuG
<!--QuoteBegin--></div><table border='0' align='center' width='95%' cellpadding='3' cellspacing='1'><tr><td>Цитата </td></tr><tr><td id='QUOTE'><!--QuoteEBegin-->кстати, может запостишь эту задачу?<!--QuoteEnd--></td></tr></table><div class='postcolor'><!--QuoteEEnd-->
А я же всё написал уже Задача абсолютно такая же, только цифры разные.

В тюрьме сидят 100 узников. Вечером им говорят, что их всех завтра на рассвете поведут казнить. Выстроят в шеренгу так, что каждый будет видеть впереди идущих, и, естественно, не сможет видеть тех, кто сзади (т.е. друг за другом). Каждому наденут на голову шапочку, но он не будет знать какого она цвета (каждая шапочка может быть либо чёрной, либо белой). А затем у каждого из них по очереди, начиная с последнего идущего (который видит всех узников, но которого не видит ни один узник), спросят: «Какого цвета шапочка у тебя на голове?». В случае, если человек угадывает цвет, его оставляют в живых, иначе – нет.
У них есть ночь на размышление, чтоб договориться, придумать систему ответов, чтоб количество выживших было МАКСИМАЛЬНЫМ.

Вот и всё (сделал копи/паст, да поправил цифры и цвета )

[Dutchman]

Кстати, а какое число максимальное?
2Флинт
А твоя задача не свкдется у десятикратному повторению предыдущей?