|
|
 |
Условие
В комнате находится несколько детей и куча из 1000 конфет. Дети по очереди подходят к куче. Каждый подошедший делит количество конфет в куче на количество детей в комнате, округляет (если получилось нецелое), забирает полученное число конфет и выходит из комнаты. При этом мальчики округляют вверх, а девочки – вниз. Докажите, что суммарное количество конфет у мальчиков, когда все выйдут из комнаты, не зависит от порядка детей в очереди.Решение
Деление с остатком кучи конфет на $k$ детей можно представлять себе так: мы раскладываем конфеты на $k$ кучек, которые либо одинаковы (если остаток 0), либо в части кучек конфет на 1 больше, чем в остальных (количество таких куч равно остатку).
Пусть первый ребёнок разложит так конфеты на кучки, расположив кучи слева направо по возрастанию числа конфет в них. Можно считать, что он возьмёт себе правую кучку, если он мальчик, или левую, если он – девочка.
Когда зайдёт следующий ребёнок, конфеты уже будут разложены на кучки, как если бы он сам делил с остатком (ведь и число детей, и число куч уменьшилось на 1), и снова мальчик возьмёт правую кучу, а девочка – левую, и т.д. В итоге мальчики возьмут все правые кучки в количестве, равном числу мальчиков, что не зависит от порядка детей в очереди.
