|
|
 |
Условие
В комнате находится несколько детей и куча из 2021 конфеты. Каждый из них по очереди подходит к куче, делит количество конфет в ней на количество детей в комнате (включая себя), округляет (если получилось нецелое число), забирает полученное число конфет и покидает комнату. При этом мальчики округляют вверх, а девочки – вниз. Докажите, что суммарное количество конфет у мальчиков, когда все выйдут из комнаты, не зависит от порядка детей в очереди.Решение
Первое решение. Докажем, что если поменять местами любых двух соседних детей, то количество конфет у мальчиков и у девочек не изменится. Так как такими перестановками можно добиться любого порядка детей в очереди, то это и будет означать, что общее количество конфет у мальчиков не зависит от этого порядка.
В самом деле, ясно, что если поменять местами двух девочек или двух мальчиков, то для детей ни до, ни после этой пары ничего изменится, не изменится и общее количество конфет у мальчиков.
Теперь пусть осталось всего $k$ детей, и перед кучей из $n$ конфет стоит пара мальчик и девочка. Если $n$ делится на $k$, то легко видеть, что они оба возьмут по $\frac{n}{k}$ конфет вне зависимости от порядка. Далее будем считать, что $n$ делится на $k$ с остатком $r > 0$. Тогда $n = kq + r$, мальчик возьмет $q + 1$ конфету и оставит $(k-1)q + r - 1$ конфет, девочка за ним возьмет $q$ конфет. А если бы сначала подошла девочка, то она бы взяла $q$ конфет и оставила бы $(k-1)q + r$, а мальчик за ней взял бы $q + 1$ конфету. Таким образом, эта пара берет одно и тоже количество конфет вне зависимости от порядка, а значит, ни для них, ни для детей за ними ничего не изменится, что и требовалось.
Второе решение. Пусть всего в комнате $n$ детей, причем $2021 = an+r$, $0\le r < n$. К куче подходит первый ребенок и делит ее на кучки размером $a$ и кучки размером $a+1$ (общее количество кучек равно $n$, а кучек размером $a+1$ ровно $r$), причем все большие кучки лежат правее маленьких.
Пусть первый ребенок – мальчик, тогда он берет себе самую правую кучку и уходит. Если же это оказалась девочка, она возьмет себе самую левую кучку и тоже уйдет. Потом к конфетам подойдет следующий ребенок; перед ним лежит $n-1$ кучка из $a$ или $a+1$ конфет.
Если остались кучки обоих видов, то это означает, что неполное частное от деления количества конфет на число детей равно $a$, и далее процесс продолжается аналогично: мальчики, округляя вверх, берут себе кучки справа, девочки, округляя вниз, – слева.
Если же остались только кучки одного вида, то количество конфет делится на количество детей, и любому ребенку подходит любая кучка, то есть и в этом случае мальчики могут брать кучки справа, а девочки – слева.
Тогда в итоге мальчики заберут все правые кучки (столько, сколько было мальчиков) независимо от того, в каком порядке дети подходили за конфетами.
