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

Проект МЦНМО
при участии
школы 57
Задача 111837
Темы:    [ Десятичная система счисления ]
[ Деление с остатком ]
[ Правило произведения ]
[ Кооперативные алгоритмы ]
Сложность: 5-
Классы: 9,10,11
В корзину
Прислать комментарий

Условие

Фокусник с помощником собираются показать такой фокус. Зритель пишет на доске последовательность из N цифр. Помощник фокусника закрывает две соседних цифры чёрным кружком. Затем входит фокусник. Его задача – отгадать обе закрытые цифры (и порядок, в котором они расположены). При каком наименьшем N фокусник может договориться с помощником так, чтобы фокус гарантированно удался?


Решение

  Предположим, что при каком-то значении N фокус удастся. Тогда по каждому варианту последовательности с двумя закрытыми цифрами (пусть их количество равно k1) фокусник может восстановить исходную; значит, каждой последовательности с двумя закрытыми цифрами фокусник однозначно может поставить в соответствие восстановленную последовательность из N цифр (пусть их количество равно k2). Следовательно,  k1k2.  Отметим, что  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,  не приводя явно самого алгоритма.

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

олимпиада
Название Всероссийская олимпиада по математике
год
Год 2007
Этап
Вариант 5
Класс
Класс 11
задача
Номер 07.5.11.3
олимпиада
Название Всероссийская олимпиада по математике
год
Год 2007
Этап
Вариант 5
Класс
Класс 10
задача
Номер 07.5.10.4

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

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