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

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

Условие

Паша выбрал 2017 (не обязательно различных) натуральных чисел a1, a2, ..., a2017 и играет сам с собой в следующую игру. Изначально у него есть неограниченный запас камней и 2017 больших пустых коробок. За один ход Паша добавляет в любую коробку (по своему выбору) a1 камней, в любую из оставшихся коробок (по своему выбору) – a2 камней, ..., наконец, в оставшуюся коробку – a2017 камней. Пашина цель – добиться того, чтобы после некоторого хода во всех коробках стало поровну камней. Мог ли он выбрать числа так, чтобы цели можно было добиться за 43 хода, но нельзя – за меньшее ненулевое число ходов?


Решение

  2017 = 43·46 + 39.  Пусть среди Пашиных чисел будут 39 двоек, 46 чисел, равных 44, а остальные – единицы.
  Чтобы добиться требуемого за 43 хода, Паша выбирает 39 коробок, в которые он всегда кладёт по 2 камня – через 43 хода в них окажется по  43·2 = 86  камней. Остальные коробки он разбивает на 43 группы по 46 коробок; на i-м ходу он кладёт по 44 камня во все коробки i-й группы и по одному камню – в коробки остальных групп. Тогда через 43 хода в каждой коробке каждой группы будет по  44 + 42·1 = 86  камней, то есть во всех коробках будет поровну камней.
  Пусть Паша сделал  k < 43  ходов. Тогда в какую-то коробку A попало 44 камня за один ход, и в ней будет не меньше, чем  44 + (k – 1)·1 = 43 + k  камней. С другой стороны, поскольку  46k < 2017,  в какую-то коробку B ни на одном из ходов не попадёт 44 камня, то есть в ней будет не больше 2k камней. Поскольку  k < 43,  то  2k < k + 43,  а значит, в коробке B меньше камней, чем в A. Таким образом, Паша ещё не добился требуемого.


Ответ

Мог.

Замечания

Приведённый пример – не единственный. Например, подойдёт также набор чисел, состоящий из 42 единиц,  2017 – 43 = 1974  чисел, равных  a > 1,  и одного числа, равного  43a – 42.  Существуют даже примеры с попарно различными числами; однако проверка того, что они подходят, несколько труднее, чем для примеров, приведённых выше.

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

олимпиада
Название Всероссийская олимпиада по математике
год
Вариант 2016/2017
этап
Вариант 4
класс
Класс 10
задача
Номер 10.3

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

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