|
|
 |
Условие
Фокуснику завязывают глаза, а зритель выкладывает в ряд N одинаковых монет, сам выбирая, какие – орлом вверх, а какие – решкой. Ассистент фокусника просит зрителя написать на листе бумаги любое целое число от 1 до N и показать его всем присутствующим. Увидев число, ассистент указывает зрителю на одну из монет ряда и просит перевернуть её. Затем фокуснику развязывают глаза, он смотрит на ряд монет и безошибочно определяет написанное зрителем число.
a) Докажите, что если у фокусника с ассистентом есть способ, позволяющий фокуснику гарантированно отгадывать число для N = k, то есть способ и для N = 2k.
б) Найдите все значения N, для которых у фокусника с ассистентом есть такой способ.
Решение
a) Мысленно расположив монеты в клетках таблицы 2×k, фокусник пишет под каждым столбцом из двух клеток O, если монеты там лежат одной стороной вверх, и P – если разными сторонами. Эта комбинация сообщает ему число n от 1 до k. Если в верхней строке чётное число решек, он называет n, иначе n + k.
Пусть зритель назвал число m. Чтобы сообщить его, ассистент тоже мысленно пишет строку из O и P по тому же правилу. Он может изменить одну из букв, чтобы получить код, соответствующий числу m (при m ≤ k) или m – k (при m > k). Для этого ему достаточно перевернуть любую из монет в соответствующем столбце. Выбором верхней или нижней монеты он обеспечивает нужную чётность числа решек в верхней строке.
б) При N = 1 способ угадывания, очевидно, существует. Из а) следует, что есть способ и для N = 2m.
Комбинации орлов и решек, которые ассистент в принципе может "выдать" фокуснику, должны быть разбиты на N групп: когда фокусник видит комбинацию из i-й группы, он называет число i.
У каждой из 2N возможных комбинации есть ровно N соседей (отличающихся от неё переворачиванием одной монеты). Они должны попасть в разные группы. В частности, у каждой комбинации из первой группы есть ровно один сосед из второй группы (и наоборот). Следовательно, в первой и второй группах (и аналогично во всех остальных) комбинаций поровну. Кроме того, отсюда следует, что все 2N комбинаций распределены по группам, то есть в каждой группе 2N/N комбинаций. Поэтому 2N кратно N, то есть N – степень двойки.
Ответ
б) N – степень двойки.
Замечания
1. Баллы: 4 + 5.
2. Задача также предлагалась в Задачнике "Кванта" ("Квант", 2008, №3, зад. М2093).
