Раз никто не решил, пишу ответ.
Доказываем по индукции.
База: для N=1 очевидно.
Шаг: Объявим N монет золотыми (остальные серебряными). В каждой кучке будем сверху класть серебряные монеты, снизу золотые. Для перекладываний всегда будем брать верхнюю монету. Тогда золотые монеты никак не влияют на движение серебряных. Следовательно, рано или поздно N*(N-1)/2 серебряных монет расположатся как в условии теоремы.
докажем, что рано или поздно N золотых монет расположатся так: по одной под каждой кучкой из серебряный монет, ещё одна сама по себе
. . . . *
. . . * *
. . * * *
. * * * *
0 0 0 0 0
Доказываем по индукции более общий факт: при любом числе золотых монет от 0 до N, рано или поздно под каждой кучкой серебряных монет останется не более одной золотой монеты, и ещё не более одной - отдельно.
. . . . *
. . . * *
. . * * *
. * * * *
0 . 0 . 0
Доказательство по индукции: при 0 золотых монет утверждение очевидно.
При числе золотых монет > 0, объявим одну из золотых монет фальшивой, и будем её всегда класть вниз кучки. Так как фальшивая монета не влияет на движение настоящих, рано или поздно настоящиe расположатся как в условии. Если фальшивая монета при этом окажется в "дырке" (т.е. под кучкой серебряных монет, где нет золотой монеты, или отдельно лежащей, и другой отдельно лежащей золотой монеты нет), условие выполнено.
. . . . *
. . . * *
. . * * *
. * * * *
0 . 0 Х 0
Если же нет, то расположим кучки в порядке возрастания числа серебряных монет. Нетрудно убедиться, что при каждом перекладывании настоящие золотые монеты циклически сдвигаются на 1 влево и описывает полный оборот за N шагов. Фальшивая же монета описывает полный оборот за N+1 шаг, т.е. за N шагов сдвигается относительно настоящих монет на 1 вправо. Следовательно, не более чем через N*(N-1) шаг она попадёт в дырку и условие будет выполнено.
| 
Новости
Чаты
88:88 
