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