Людоед поймал сто мудрецов [ это задачка такая ]

Итак, задача такая:
Людоед поймал сто мудрецов и сказал: "Каждому из вас я напишу на лбу целое число от 1 до 100. Числа могут повторяться, могут хоть все быть одинаковыми. Вы сможете посмотреть друг на друга, то есть каждый увидит, что написано на лбу у остальных 99, но не увидит, что написано на лбу у него самого. Потом каждый должен сказать мне, что, по его мнению, написано на лбу у него. Ответов друг друга вы, естественно, не услышите, и подсказать не удастся. Если хотя бы один из вас угадает свое число, я всех отпущу, а если никто не угадает - всех съем. Перед тем, как числа будут написаны, можно о чем-нибудь договориться."
Вопрос, естественно, - какую стратегию избрать мудрецам?

Сказать друг другу что у них написано на лбу - по условиям задачи это не запрещено )

Запрещено.

Они договариваются:
- каждому присваивается номер: 1, 2...100
- тот, кто увидит на другом свой номер, шепчет людоеду. Это видят другие, и все называют этот номер. Поскольку хоть на ком-то этот номер написан, хоть кто-то угадает.

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

Договориться можно вот о чем: после нумерации, все молча ищут лоб с номером 1, собираются вокруг него. Если номеров 1 несколько, выталкивают их в центр круга и пускают первыми на допрос к людоеду. Пока те на допросе, толпа в круг выталкивает номера 2. И так до самого конца.

Вообще договариться можно еще много о чем. Вероятность пожрать у людоеда при таком раскладе минимальна.

Perpetum Mobile, ну и вытолкнули, ну и что? Вытолкнутый-то не знает своего номера. Первым, например, могли вытолкнуть с номемером 2, если нет номера 1.

Я так понял, что не очень внятно изложил свое решение.

Они договариваются:
- каждому присваивается номер: Иван -1, Прохор - 2..., Никита - 100. Номера каждого все запоминают;
- тот, кто увидит на другом свой номер, шепчет людоеду. Например, Прохор, увидел на ком-то номер 2 -- он что-то шепчет (например, "87"). Это видят другие, и знают, что поскольку Прохор имел право назвать только свой тномер (2), то на ком-то есть номер 2. Все называют этот номер. Поскольку хоть на ком-то этот номер написан, хоть кто-то угадает.

Perpetum Mobile, Роман после того, как номера на лбах написаны, мудрецы не могут никаким образом передать никакую информацию друг другу. То есть каждый мудрец может узнать только номера, написанные на лбах у его товарищей по несчастью.
Это вполне настоящая задачка, в стиле олимпиадных задач для школьников. Мне сын ее рассказал, откуда взял - не знаю. Он ее решил, а я - нет Но решение знаю

Где в моем решении ту увидела передачу информации после того, как номера на лбах написаны? Я предланал, что каждый получает некоторый условный номер и все его запоминают до того, как номера на лбах написаны. Вероятно, есть и другое решение.

Роман:

Вот тут увидела:

Что-то сказать людоеду должен каждый. Можно считать, что людоед сначала разводит их по отдельным камерам, а потом опрашивает.

Сообщение отредактировал(а) Старуха Шапокляк - 16.11.2009 - 14:00

Задача, похоже, имеет красивое решение. Например, стратегия для 2 мудрецов и 2 чисел: один называет то, что видит, другой -- то, что не видит. А далее для 3 и т.д. уже лень голову ломать.

Действительно, имеет. Если никто его не придумает, я дня через три напишу. Или подсказать сначала немножко?

Не надо. Не ломай кайф.

раз они могут договориться, то нужно наверное идти в сторону сколько парных и непарных чисел от 1 до 100...но вот как определить какое именно...нужно подумать.

на подходе к решению:
А если 1 мудрец строит всех в шеренгу по возрастанию видимых ему чисел.
А его самого на место поставит кто то другой.
Если справа и слева от какого то мудреца такое же число - он знает, что и у него такое. Так что - если есть 3 одинаковых - задача решена.
Если никто не завопил по такому алгоритму - есть только одинаковые пары... тут надо подумать.

Обобщенно - по тризу - надо искать ==законный== с точки зрения людоеда способ обмениваться инфой.
Первый способ - упорядочивание.

По условию, после нумерации мудрецы стоят, молчат и смотрят.

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