|
|
 |
Условие
Чётное число орехов разложено на три кучки. За одну операцию можно переложить половину орехов из кучки с чётным числом орехов в любую другую кучку. Докажите, что, как бы орехи ни были разложены изначально, такими операциями можно в какой-нибудь кучке собрать ровно половину всех орехов.
Решение
Заметим, что если мы добьёмся размеров кучек 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 станут равны.
