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

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

Условие

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

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

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

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

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

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