Двоичные карточки

При­думан­ный в начале 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$. Именно эти числа и стоят пер­выми на тех кар­точ­ках, при показе кото­рых зри­тель дал утвер­ди­тель­ный ответ.

Другие модели раздела «Числа и их свойства»