И снова головоломка Дж. Фолька

Об авторе этой игрушки, шотландце Джеймсе Фольке, и его головоломке мы писали в "Левше" № 12 за 1998 г. Вкратце напомним ее конструкцию. В длинном деревянном бруске пропилен паз, имеющий выход только с левого торца (см. рис.). По пазу свободно перемещается рейка. Вся эта конструкция очень напоминает логарифмическую линейку. Рейку можно полностью вытянуть из бруска и вновь задвинуть в него до упора. Еще тогда мы обратили внимание читателей, что легкость вытягивания рейки кажущаяся. Стоит только повернуть относительно оси хотя бы один из шести дисков, как срабатывает запирающий механизм и рейку "заклинивает".
Объяснив принцип действия и технологию изготовления головоломки Фолька, мы предложили читателям самим поискать решение. И вот получаем долгожданное письмо от Степана Молоченко из Луцка, который не просто нашел решение головоломки, но и с математической точностью рассчитал формулу и последовательность шагов. Впрочем, вы сами можете в этом убедиться.

Прежде всего Степан предлагает внести обозначения (см. рис.). "0" - это когда диск своей выпуклой стороной смотрит влево. А когда выпуклая сторона опущена вниз - "I". Понятно, что только тогда, когда все диски выставлены в положении "0", рейка легко выдвинется из бруска. А теперь посмотрим, как же решается головоломка. Степан приводит две таблицы, которые показывают, как можно кратчайшим путем прийти к правильному решению. Приводим их полностью.
Нетрудно подсчитать, что минимальное число перестановок для шести дисков будет 42. Более того, есть, оказывается, строгая математическая зависимость между числом дисков и числом перестановок. Как получена эта зависимость, в письме Степана мы не нашли. Но то, что она верна, легко убедится каждый. Вот его формула:

где N - число перестановок, а n - число дисков. Нетрудно подсчитать, что для семи дисков число перестановок будет 85, а для восьми - 170.