Встеретил задачу http://codeforces.net/gym/100197

Суть в том что надо n колец перетащить с одной ячейки на другую. Надо найти мин. количество перекладываний. Всего ячеек m. В обычных башнях n колец и 3 ячейки.

Решение,вероятно, такое:

Рассмотрим перекладывание самого большого кольца. Оно естественно будет одно, с начальной позиции на конечную. У нас останется n — 2 ячейки с какими-то кольцами. Если доказать, что в каждой ячейки будет последовательный отрезок колец (тоесть 1-2-3 или 10-11-12-13), то можно придумать динамику. Я просмотрел решения, примерно такое и пишут. Но как доказать этот факт?