ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам | Поиск |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 64591
Темы:    [ Кооперативные алгоритмы ]
[ Примеры и контрпримеры. Конструкции ]
[ Разбиения на пары и группы; биекции ]
[ Правило произведения ]
Сложность: 4
Классы: 9,10,11
В корзину
Прислать комментарий

Условие

Автор: Грибок С.

Фокуснику завязывают глаза, а зритель выкладывает в ряд 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

Источники и прецеденты использования

олимпиада
Название Турнир городов
Турнир
Номер 29
Дата 2007/2008
вариант
Вариант осенний тур, сложный вариант, 10-11 класс
задача
Номер 5

© 2004-... МЦНМО (о копирайте)
     
Пишите нам
Rambler's Top100

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .