Задача 67467
|
|
 |
Условие
Фокусник вместе со своим помощником собираются показать следующий фокус. Помощник надевает фокуснику повязку на глаза, приглашает на сцену случайного зрителя из зала и просит его написать последовательность из нулей и единиц длины $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$ цифр.
Замечания
Утверждение задачи остаётся верным при замене 2025 на произвольное натуральное $k$.Покажем также, что фокусник и помощник не смогут договориться так, чтобы отгадать больше, чем $k$ бит последовательности, состоящей из $2^k$ бит. Предположим противное: фокусник всегда может определить $k+1$ бит. Он может получить от помощника $2^{k+1}$ различных сообщений, так как полученный бит может иметь $2^{k}$ номеров и может иметь 2 возможных значения. Пусть $A$ – множество таких пар (номер и значение). Для каждой такой информации фокусник должен уметь определять значение $k+1$ бит. Для каждого элемента $a \in A$ пусть $S_a$ – множество битовых последовательностей длины $2^{k}$, у которых $k+2$ бита (вместе с тем битом, что раскрыл помощник), угаданные фокусником для элемента $a$, совпадают с действительными значениями. Тогда $\left|S_a\right| \leqslant 2^{2^{k}-(k+2)}$. Более того, для любой битовой последовательности $x$ длины $2^k$ помощник отправляет сообщение $a \in A$, для которого фокусник правильно определяет $k+2$ бита этой последовательности, то есть $x \in S_a$. Следовательно, $\bigcup_{a \in A} S_a$ – это в точности все битовые последовательности длины $2^k$. Однако $$ \Bigl|\mkern2mu{\textstyle\bigcup\limits_{a \in A} S_a}\Bigr| \leqslant \sum_{a \in A} |S_a| \leqslant 2^{k+1} \cdot 2^{2^{k}-(k+2)}<2^{2^k}. $$ Противоречие.
