|
|
 |
Условие
Фокусник с помощником собираются показать такой фокус. Зритель пишет на доске последовательность из N цифр. Помощник фокусника закрывает две соседних цифры чёрным кружком. Затем входит фокусник. Его задача – отгадать обе закрытые цифры (и порядок, в котором они расположены). При каком наименьшем N фокусник может договориться с помощником так, чтобы фокус гарантированно удался?
Решение
Предположим, что при каком-то значении N фокус удастся.
Тогда по каждому варианту последовательности с двумя закрытыми цифрами (пусть их количество равно k1) фокусник может восстановить исходную; значит, каждой последовательности с двумя закрытыми цифрами фокусник однозначно может поставить в соответствие восстановленную последовательность из N цифр (пусть их количество равно k2). Следовательно, k1 ≥ k2. Отметим, что k1 = (N – 1)10N–2 (есть N – 1 вариант вычеркнуть две цифры, а на остальные N – 2 позиции есть по 10 вариантов на каждую). А k2 = 10N . Значит, N – 1 ≥ 100, то есть N ≥ 101.
Покажем, как выполнить фокус при N = 101. Пусть сумма всех цифр на нечётных позициях имеет остаток s от деления на 10, а сумма всех цифр на чётных позициях имеет остаток t от деления на 10 (позиции нумеруются слева направо числами от 0 до 100). Положим p = 10s + t. Пусть помощник закроет цифры, стоящие на позициях p и p + 1. Увидев, какие цифры закрыты, фокусник определит p, а следовательно, определит s и t. Отметим, что одна закрытая цифра стоит на нечётной позиции, а другая – на чётной. Таким образом, вычислив сумму открытых цифр на нечётных позициях и зная s, фокусник определит закрытую цифру, стоящую на нечётной позиции.
Аналогично определяется закрытая цифра, стоящая на чётной позиции.
Ответ
При N = 101.
Замечания
Применяя теорему о сватовстве (см. решение задачи 98160), можно доказать существование алгоритма действий фокусника и его помощника при
N = 101, не приводя явно самого алгоритма.
