Процессы и алгоритмы

Занумеруем камни от до Занумеруем коробки от до по или против часовой стрелки так, чтобы все камни в начале были в -й коробке, а в конце оказались в -й.

Расставим бесконечное количество кувшинов в ряд (у каждого кувшина будет номер целое число). Положим в кувшин с нулевым номером шаров, занумерованных от до Каждый ход, когда камень с номером перекладывают из коробки номер в коробку номер будем перекладывать шар номер из кувшина где он находился на момент перекладывания камня, в кувшин номер

Аналогично, когда камень с номером перекладывают из коробки номер в коробку номер будем перекладывать шар номер из кувшина где он находился на момент перекладывания камня, в кувшин номер Таким образом, одновременно с перекладыванием двух камней мы будем перекладывать два шара. Заметим, что остаток по модулю от номера кувшина, в котором находится -й шар, будет всегда равен номеру коробки, в котором находится -й камень.

Обозначим номер кувшина, в котором находится -й шар в данный момент, за Мы только что выяснили, что тогда номер коробки, в котором находится -й камень, равен Теперь ясно, что в конце все шары оказались в кувшинах, номера которых сравнимы с по модулю Заметим, что сумма

в любой момент времени равна нулю: в начале она равна нулю, так как все шары были в кувшине с номером и каждый ход одно из слагаемх увеличивается на а другое — уменьшается.

Поскольку ни один из шаров в конце не находится в кувшине номер один из шаров, допустим -й, оказался в конце в кувшине с отрицательным номером. Поскольку этот номер сравним с по модулю номер кувшина -го шара в конце концов оказался меньше либо равен

Итого, номер кувшина -го шара каждый ход менялся не более, чем на и в конце стал меньше либо равен Но это значит, что остатки от деления на номера кувшина -го шара пробежали все возможные значения от (в начале) до То есть номер коробки -го камня пробежал все возможные значения от до что и требовалось.