Тест на околпачивание

[fortpost]

Для прохождения теста тысячу мудрецов выстраивают в колонну. Из колпаков с номерами от 1 до 1001 один прячут, а остальные в случайном порядке надевают на мудрецов. Каждый видит только номера на колпаках всех впереди стоящих. Далее мудрецы по порядку от заднего к переднему называют вслух целые числа. Каждое число должно быть от 1 до 1001, причем нельзя называть то, что уже было сказано. Результат теста – число мудрецов, назвавших номер своего колпака. Мудрецы заранее знали условия теста и могли договориться, как действовать.  Как мудрецам получить наилучший результат?

[Tim]

Показать скрытый текст

Есть подозрение, что 999 и доказывать надо через четность/нечетность количества инверсий, но это уже выше моих познаний

[fortpost]

Показать скрытый текст

Есть подозрение, что 999 и доказывать надо через четность/нечетность количества инверсий, но это уже выше моих познаний

В правильном направлении движетесь!

[Руслан Дехтярь]

del

[Руслан Дехтярь]

del

[Руслан Дехтярь]

Показать скрытый текст

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

[Nata_Lisa]

Показать скрытый текст

А что если первому говорящему просто назвать сумму своего и недостающего. Тогда следующий вычислит свой номер, назовет его. И т.д.

Хм... проблемка, если это число больше 1001, и если кому-то придется повториться...

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

А, всё сходится. Тот мудрец, который не может назвать свой номер, называет любой из первых двух (первого и спрятанный). Он их тоже знает. Получается, что ровно 998 мудрецов правильно ответят.

[Tim]

Показать скрытый текст

Почитал про перестановки, получается как-то так:
1. Последний не видит 2 номеров (свой и отброшенный), и для них есть два варианта расположения. В одном из вариантов перестановка четная, в другом нечетная.
2. Мудрецы договорились, что последний называет свое число так, чтобы перестановка была четной.
3. Следующий не знает своего номера и отброшенного. При этом существует только один вариант сохранить перестановку четной, исходя из этого он и называет номер.
4. Таким образом, из 1000 - 999 определяют номера однозначно, 1 с вероятностью 50%

[fortpost]

Tim0512 - браво!!!
RD, Nata_Lisa - маладцы-ы-ы!!!