Назад
Задача

Фокусник вместе со своим помощником собираются показать следующий фокус. Помощник надевает фокуснику повязку на глаза, приглашает на сцену случайного зрителя из зала и просит его написать последовательность из нулей и единиц длины $2^{2025}$. Затем помощник верно называет фокуснику номер и значение некоторого одного члена последовательности. Задача фокусника – отгадать $2025$ других членов последовательности (то есть назвать их номера и значения). Докажите, что они могут заранее договориться так, чтобы фокус удался.

Решение

Пусть $A$ – множество всех последовательностей из нулей и единиц длины $2^{2025}$. Определим функцию $f(a)$, сопоставляющую каждой последовательности $a$ из $A$ последовательность, состоящую из её последних $2025$ цифр. Пусть $B$ – множество всех последовательностей из нулей и единиц длины $2025$, в которых ровно один элемент равен 1, а $C$ – множество всех остальных последовательностей длины $2025$. Тогда $|B| = 2025$, $|C| = 2^{2025} - 2025$. Введём функцию «нумерации» для последовательностей из $C$, то есть функцию $g\colon C \to {1, 2, 3, \ldots, 2^{2025} - 2025}$, взаимно однозначно сопоставляющую каждой последовательности из $C$ какой-то номер от $1$ до $2^{2025} - 2025$. Обе функции $f$ и $g$ известны как фокуснику, так и его помощнику. Теперь опишем действия каждого из них. Пусть помощник увидел перед собой последовательность $x$. Тогда у него есть несколько вариантов.

  1. Если $f(x) \in C$, то он сообщает значение элемента под номером $g(f(x))$.
  2. Если $f(x) \in B$ и первая цифра последовательности $x$ равна $1$, то помощник сообщает значение и номер единицы из последовательности $f(x)$.
  3. Если $f(x) \in B$ и первая цифра последовательности $x$ равна 0, то помощник сообщает значение и номер того нуля, который следует за единственной единицей в последовательности $f(x)$ (такая единица единственна, так как эта последовательность принадлежит множеству $B$). Если же единица стоит на последнем месте, то помощник сообщает значение и номер первого нуля. Опишем действия фокусника. Если он услышал цифру с номером из диапазона от $1$ до $2^{2025} - 2025$, то он понимает, что это случай 1). Значит, по этому номеру с помощью функции нумерации (ввиду её биективности) он может восстановить $f(x)$, а значит, и последние $2025$ цифр вместе с их номерами. Если он услышал цифру с номером из последних 2025 номеров, то он понимает, что это случай 2) или 3). Но в обоих случаях среди последних 2025 цифр последовательности $x$ все, кроме одной, нули. Из последних 2025 цифр он может отгадать $2024$ других цифры, так как одну уже назвал помощник. Также он может назвать самую первую цифру последовательности, так как она в случаях 2) и 3) совпадает с той цифрой, что называет помощник. Значит, и в этом случае фокусник отгадает $2025$ цифр.
Ответ

Ответ задачи отсутствует

Чтобы оставлять комментарии, войдите или зарегистрируйтесь

Комментариев нет