|
|
 |
Условие
Для прохождения теста тысячу мудрецов выстраивают в колонну. Из колпаков с номерами от 1 до 1001 один прячут, а остальные в случайном порядке надевают на мудрецов. Каждый видит только номера на колпаках всех впереди стоящих. Далее мудрецы по порядку от заднего к переднему называют вслух целые числа. Каждое число должно быть от 1 до 1001, причём нельзя называть то, что уже было сказано. Результат теста – число мудрецов, назвавших номер своего колпака. Мудрецы заранее знали условия теста и могли договориться, как действовать.
а) Могут ли они гарантировать результат более 500?
б) Могут ли они гарантировать результат не менее 999?
Решение
а) Пусть задний мудрец назовёт остаток от деления на 1001 суммы чисел, которые он видит (называя 1001, если остаток 0). Тогда следующий может вычислить своё число, отняв от названного сумму того, что видит. Так продолжается, пока чье-то вычисленное число не совпадет с тем, что назвал задний. Тогда этот неудачник вместо своего числа назовёт число самого переднего мудреца. По договоренности остальные поймут, что он имел в виду число заднего, и будут далее действовать исходя из этого. В итоге ответят правильно все мудрецы, кроме, возможно, заднего, неудачника и переднего.
б) Пусть спрятанный колпак лежит за спиной заднего мудреца. Тогда номера колпаков образуют перестановку. Задний не видит двух номеров, и для них есть два варианта расположения. В одном из вариантов перестановка чётная (а в другом – нет). В соответствии с этим вариантом задний свой номер и называет (ошибаясь с вероятностью 50%). В полученной чётной перестановке второй сзади не знает расположения только двух номеров: своего и того, который, по мнению первого, лежит позади. Есть два варианта расположения неизвестных номеров, и лишь в одном из них перестановка чётна. В соответствии с этим второй правильно вычисляет свой номер. Точно так же все остальные последовательно вычисляют свои номера. В результате правильно ответят все, кроме, быть может, заднего.
Ответ
Могут (в обоих случаях).
Замечания
баллы: 5 + 7
