Придуманный в начале XIX века классический фокус по отгадыванию задуманного числа позволит вам удивить ребёнка, представ перед ним в роли математического мага и заинтересовать его изучением двоичной системы счисления.
- Зритель загадывает натуральное число от $1$ до $100$.
- Зритель указывает карточки, на которых присутствует загаданное число. (Для удобства числа на каждой карточке выписаны в порядке возрастания.)
- Фокусник в уме складывает первые числа указанных карточек и торжественно называет загаданное число.
Проведя несколько опытов, можно убедиться, что приведённое правило работает. В чём же секрет карточек? Можно ли обойтись меньшим количеством карточек для гарантированного отгадывания одного числа из $100?$ Чтобы ответить на эти вопросы, вспомним самые основы теории информации и двоичную систему счисления.
Следуя Клоду Шеннону, бит — это количество информации, уменьшающее «незнание» ровно в два раза. Именно столько информации получает фокусник, когда зритель говорит, присутствует или нет на карточке указанное число.
Исходно незнание фокусника равно $100$ — ему предстоит выбрать одно число из ста возможностей. В самом удачном случае — при правильно составленных карточках (вопросах) — за один ответ зрителя незнание фокусника уменьшится вдвое. Т. е. после первого ответа незнание будет не менее $50$, после второго — $25$ и т. д. После шести ответов незнание может быть всё ещё больше $1$ — значит, единственный вариант гарантированно выбрать нельзя. Поэтому никаких шести карточек в общем случае не достаточно для определения числа от $0$ до $100$. А вот после седьмого ответа незнание становится меньше $1$ — при правильно составленных карточках выбор однозначен (на самом деле, выбор однозначен даже если рассматривать числа от 1 до 128). Осталось эту теорию реализовать на практике.
Ответы зрителя «нет» и «да» можно кодировать числами $0$ и $1$. Условимся во всех опытах показывать карточки в одном и том же порядке (скажем, от первой к седьмой). Тогда полный ответ зрителя — упорядоченная последовательность длины $7$, составленная из нулей и единиц. Пусть, для наглядности, будет $0110011$. Для реализации фокуса надо научиться всевозможным таким последовательностям взаимно однозначно сопоставлять натуральные числа. Но зачем что-то придумывать, если есть двоичная система счисления!
Приведённой последовательности $0110011$, если её рассматривать как двоичную запись, соответствует число
$0\cdot 2^6\ +$ $1\cdot 2^5\ +$ $1\cdot 2^4\ +$ $0\cdot 2^3\ +$ $0\cdot 2^2\ +$ $1\cdot 2^1\ +$ $1\cdot 2^0 =$ $32 + 16 + 2 + 1 = 99.$
Теперь несложно догадаться и как устроены карточки: на карточке с номером $n$ выписаны все числа, в двоичной записи которых в $n$-м разряде стоит $1$ (будем считать младший разряд первым, старший — седьмым). Как и хотели, каждый ответ зрителя ровно в два раза уменьшает множество чисел, в котором находится задуманное число, — ведь в двоичной системе цифр всего две: в каждом разряде стоит $0$ или $1$. Причём при поочерёдном показе карточек все ответы независимы — каждый раз спрашивается про следующий разряд, и никакие два ответа зрителя не дают одну и ту же информацию.
Выписывание чисел на каждой карточке по возрастанию не только является удобным для зрителя, но и даёт эффективный для фокусника способ обработки полученной информации. Число из примера является суммой «базисных»: $0110011 =\ $$0100000\ +$ $0010000\ +$ $0000010\ + $ $0000001$. Именно эти числа и стоят первыми на тех карточках, при показе которых зритель дал утвердительный ответ.
