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

[Флинт]

2Dutchman
Нет, не сводится. Блин, подсказка уже получается, ну да ладно, всё равно такой вывод быстро делается: алгоритм не зависит от числа узников.

[Bastion]

М-да, подумал тут на досуге, на каждый разклад получается своя цепочка рассуждений, просчитал пока для 9 одинаквыз и 8+1, считаю в голове (без бумаги) и преиодически запутываюсь , но интересно, блин...

[Mutter Duhastovich]

Вопрос: может ли заключенный на вопрос какого цвета твоя шапочка. ответить например: я не знаю. И получить шанс ответить еще раз но уже назвать один из 4х цветов.

[Флинт]

2Mutter Duhastovich
Нет. Ему задают один вопрос, он даёт один ответ, говоря ровно одно слово из четырёх возможных вариантов.

[YuG]

Ну вот я и вернулся... Эх, хорошо погуляли
Лады, теперь мои комментарии. По порядку:
2Флинт
Я знаю решение твоей задачи
2Dutchman
<!--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-->
Я могу, конечно, написать ответ, но это уже будет подсказка, а договорились, что их не будет, поэтому, если хочешь, пиши мне в ЛС (или внимательнее читай предыдущие мои посты - там почти явно написан ответ)
<!--QuoteBegin--></div><table border='0' align='center' width='95%' cellpadding='3' cellspacing='1'><tr><td>Цитата </td></tr><tr><td id='QUOTE'><!--QuoteEBegin-->
2Флинт
А твоя задача не свкдется у десятикратному повторению предыдущей?
<!--QuoteEnd--></td></tr></table><div class='postcolor'><!--QuoteEEnd-->
нет, у них решение аналогичное
2Mutter Duhastovich
<!--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-->
конечно может - кто же ему запретит ))
<!--QuoteBegin--></div><table border='0' align='center' width='95%' cellpadding='3' cellspacing='1'><tr><td>Цитата </td></tr><tr><td id='QUOTE'><!--QuoteEBegin-->
И получить шанс ответить еще раз но уже назвать один из 4х цветов.
<!--QuoteEnd--></td></tr></table><div class='postcolor'><!--QuoteEEnd-->
дык, эта ... У него уже головы не будет... Какой шанс? Чем он будет отвечать?

[Bastion]

Ну, в общем, похоже решил я эту задачу, правда нужно сказать, что для начала нужно было решить черно-белую, кстати совершенно пофигу скока будет узников...

[Bastion]

2YuG
Похоже про задачу забыли, давай подождем до понедельника, а там выложишь решение...

[YuG]

Лады... Правда, для этого мне самому нужно вспомнить решение

[YuG]

Кстати, понедельник пришел...
Будем делиться ответом Расписал решение очень подробно, будут вопросы - задавайте...

ОТВЕТ:
Выживают все, кроме того, который стоит последним в шеренге (для него ответ: "Как повезет")

РЕШЕНИЕ:
цвета шапок кодируются цифрами (1, 2, 3, 4). Произвольно: белая - 1, желтая - 2, синяя - 3, зеленая - 4
Теперь будем считать, что узники не называют цвета, а называют числа (проще объяснять решение).
Каждый узник может посчитать сумму цифр шапок впередистоящих и сумму цифр шапок уже названных предыдущими.
Таким образом простым вычитанием он определяет цифру (а следовательно и цвет) своей шапки.
Теперь самое главное:
какое число должен назвать последний узник?
Ведь сумма всех чисел впереди него больше 4...
Он делает так:
находит N - сумма всех чисел впереди него (пусть к примеру 23)
находит К - сумма всех чисел до него (в данном случае 0)
находит М - число, удовлетворяющее условию: 0 <= (M-К-N) <4 (получаем 24)
вычитает (M-К-N) (получает 1)
называет это число (вероятность его выживания 25%)

Следующий за ним (по той же формуле):
находит N - сумма всех чисел впереди него (пусть к примеру 20)
находит К - сумма всех чисел до него (в данном случае 1)
находит М - число, удовлетворяющее условию: 0 <= (M-К-N) <4 (получаем 24)
вычитает (M-К-N) (получает 3)
называет это число (вероятность выживания 100%)

для остальных аналогично...

вот такая история...

[YuG]

Обнаружена неточность в решении:
число М должно удовлетворять условию 0 <= (M-К-N) <4 и быть кратным 4
(спасибо TankMan'у)

[Флинт]

А не проще было написать, что просто делаются сложения и вычитания по модулю 4?

[YuG]

2Флинт
не каждый поймет как это...
(это же форум не только программеров)