МОШ 2025, 11 класс, задача 5
Фокусник вместе со своим помощником собираются показать следующий фокус. Помощник надевает фокуснику повязку на глаза, приглашает на сцену случайного зрителя из зала и просит его написать последовательность из нулей и единиц длины . Затем помощник верно называет фокуснику номер и значение некоторого одного члена последовательности. Задача фокусника — отгадать других членов последовательности (т. е. назвать их номера и значения). Докажите, что они могут заранее договориться так, чтобы фокус удался.
(М. Гасанов)
Решение. Пусть — множество всех последовательностей из нулей и единиц длины . Определим функцию , сопоставляющую каждой последовательности из последовательность, состоящую из её последних цифр. Пусть — множество всех последовательностей из нулей и единиц длины , в которых ровно один элемент равен , а остальные равны , а — множество всех остальных последовательностей длины . Тогда , . Введём функцию «нумерации» для последовательностей из , т. е. функцию , взаимно однозначно сопоставляющую каждой последовательности из какой-то номер от до . Обе функции и известны как фокуснику, так и его помощнику.
Теперь опишем действия каждого из них. Пусть помощник увидел перед собой последовательность . Тогда у него есть несколько вариантов.
-
Если , то он сообщает значение элемента под номером .
-
Если и первая цифра последовательности равна , то помощник сообщает значение и номер единицы из последовательности .
-
Если и первая цифра последовательности равна , то помощник сообщает значение и номер того нуля, который следует за единственной единицей в последовательности (такая единица единственна, так как эта последовательность принадлежит множеству ). Если же единица стоит на последнем месте, то помощник сообщает значение и номер первого нуля.
Опишем действия фокусника.
-
Если он услышал цифру с номером из диапазона от до , то он понимает, что это случай 1). Значит, по этому номеру с помощью функции нумерации (ввиду её биективности) он может восстановить , а значит, и последние цифр вместе с их номерами.
-
Если он услышал цифру с номером из последних номеров, то он понимает, что это случай 2) или 3). Но в обоих случаях у нас у последовательности последние цифр все нули, кроме одного. Из последних цифр он может отгадать других цифры, так как одну уже назвал помощник. Также он может назвать самую первую цифру последовательности, так как она в случаях 2) и 3) совпадает с той цифрой, что называет помощник. Значит, и в этом случае фокусник отгадает цифр.
Замечание. Утверждение задачи остаётся верным при замене на произвольное натуральное . Также можно показать, что фокусник и помощник не смогут договориться так, чтобы отгадать других членов последовательности.