|
|
 |
Условие
Фокуснику завязывают глаза, а зритель выкладывает в ряд N одинаковых монет, сам выбирая, какие – орлом вверх, а какие – решкой. Ассистент фокусника просит зрителя написать на листе бумаги любое целое число от 1 до N и показать его всем присутствующим. Увидев число, ассистент указывает зрителю на одну из монет ряда и просит перевернуть её. Затем фокуснику развязывают глаза, он смотрит на ряд монет и безошибочно определяет написанное зрителем число.
a) Докажите, что если у фокусника с ассистентом есть способы, позволяющие фокуснику гарантированно отгадывать число для N = a и для N = b, то есть способ и для N = ab.
б) Найдите все значения N, для которых у фокусника с ассистентом есть такой способ.
Решение
a) Первый способ. Фокусник и ассистент заранее каждому целому числу от 1 до ab сопоставляют пару целых чисел (i, j), где
1 ≤ i ≤ a и 1 ≤ j ≤ b: записывают целые числа от 1 до ab в табличку a×b и числу, стоящему на пересечении i-й строки и j-го столбца, сопоставляют пару (i, j). Теперь, чтобы восстановить число, фокуснику достаточно угадать пару чисел (i, j), которая сопоставлена этому числу.
Действия фокусника: мысленно расположив монеты в виде прямоугольника a×b , фокусник пишет справа от горизонтального ряда монет O, если в нём чётное число орлов, и P – в противном случае. Так он получает комбинацию из a орлов и решек. По тому же правилу он пишет О или Р под каждым вертикальным рядом монет, получая комбинацию из b орлов и решек. Эта пара комбинаций и сообщает ему пару чисел: i от 1 до a, и j от 1 до b. Заглянув в таблицу a×b , заполненную числами от 1 до ab, фокусник называет число на пересечении i-й строки и j-го столбца.
Действия ассистента: он тоже мысленно выписывает две комбинации орлов и решек по тем же правилам. Пусть названное зрителем число находится в табличке с числами на пересечении i-й строки и j-го столбца. Чтобы сообщить i по способу для a монет, ассистенту надо изменить k-ю позицию в комбинации справа от прямоугольника. Аналогично для сообщения j ему надо изменить l-ю позицию в комбинации под прямоугольником. Тогда он просто переворачивает монету на пересечении k-го горизонтального ряда и l-го вертикального ряда в прямоугольнике.
Второй способ. Как следует из задачи 64585 б), a и b – степени двойки. Тогда и ab – степень двойки, и по задаче 64585 а) способ существует.
б) См. задачу 64585 б).
Замечания
баллы: 4 + 4
