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

Проект МЦНМО
при участии
школы 57
Задача 65670
Темы:    [ Процессы и операции ]
[ Четность и нечетность ]
Сложность: 4
Классы: 7,8,9
В корзину
Прислать комментарий

Условие

Чётное число орехов разложено на три кучки. За одну операцию можно переложить половину орехов из кучки с чётным числом орехов в любую другую кучку. Докажите, что, как бы орехи ни были разложены изначально, такими операциями можно в какой-нибудь кучке собрать ровно половину всех орехов.


Решение

  Заметим, что если мы добьёмся размеров кучек x, 2x и y, то мы сможем получить кучки размеров x, x и  x + y,  где  x + y  чётно, а далее – размеров x,
½ (3x + y)  и  ½ (x + y),  где в средней кучке ровно половина орехов.
  Опишем алгоритм, по которому можно получить нужные размеры кучек. Выберем пару кучек так, чтобы хотя бы одна была чётной:  (2m, n).  Если
m = n,  то мы у цели. Пусть  m ≠ n.  Будем преобразовывать пару так, чтобы всегда оставалась чётная кучка, а общее число орехов в паре либо уменьшалось, либо сохранялось, но при сохранении уменьшался модуль разности  |m – n|.  А именно, если m или n чётно, то переложим m орехов в третью кучку, при этом общее число орехов в паре уменьшится. Если m и n нечётны и не равны, то переложим m орехов из одной кучки в другую, получив пару  (m, m + n).  При этом  m + n чётно, и  |½ (m + n) – m| = ½ |n – m| < |m – n|.  Поскольку уменьшать и общее число орехов, и разность  |m – n| можно лишь конечное число раз, рано или поздно m и n станут равны.

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

олимпиада
Название Московская математическая олимпиада
год
Год 2016
Номер 79
класс
Класс 8
задача
Номер 6

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

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