Автор задачі: | Йосиф Ентін |
Задачу підготував: | Павло Цікалишин |
Розбір написав: | Костянтин Денисов |
Оптимальний порядок перестановки кубиків можна описати наступним чином:
Спочатку правильно складаємо останній стовпчик за n+2 операції:
Перемістимо кубик з першого стовпчика на другий;
Перемістимо кубик з останнього стовпчика на перший;
Далі вже без перешкод за операцій можна буде скласти останній стовпчик, просто переміщаючи кубики , , ..., .
Далі будемо продовжувати складати стовпчики починаючи з кінця, але тепер на складання стовпчика витратимо i+1 операцію, а не i+2, як для останнього стовпчика;
Для складання стовпчика будемо діяти таким чином:
Перемістимо єдиний кубик зі стовпчика на стовпчик i+1 (в попередньому випадку не було такого стовпчика);
Далі за операцій можна буде скласти стовпчик, переміщаючи кубики , , ..., .
Після правильного складання стовпчиків з по перший стовпчик автоматично буде складений, тому додаткові операції на нього не знадобляться.
Тоді сумарно витратимо (n+2)+n+(n-1)+\ldots+3=n+2+\frac{n \cdot (n+1)}{2} - 3=\frac{n^2+3 \cdot n - 2}{2} операцій.