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

Посмотрим, что происходит с конфигурациями, в зависимости от того, как расположены первая и последняя монеты

• Если первая лежит буквой кверху, то последние монет преобразуются по аналогичным правилам так, словно первой монеты нет (пока все не превратятся в ). После преобразований последних монет последняя монета переворачивается.
• Если последняя монета лежит буквой кверху, то она никогда не будет перевернута, а первые монет преобразуются так, будто последней монеты нет.
• Если конфигурация начинается монетой, повернутой кверху буквой и заканчивается монетой, повернутой кверху буквой то средние монеты преобразуются по правилам так, будто других монет нет, пока все не повернутся буквой После этого сначала по порядку переворачиваются монеты а затем по порядку переворачиваются монеты

Таким образом, рассмотрены все возможные конфигурации и очевидно, что для и процесс конечен. По индукции получаем, что он конечен для любого натурального

Определим где — среднее число ходов преобразования конфигурации длиной которые начинаются на если не является и оканчиваются на если не является Тогда при имеем

• 
• 
• исходя из замечаний для и
• 

Таким образом, выполняются равенства

Тогда получаем

и аналогичным образом

Теперь получаем реккурентное выражение для

Поскольку, мы знаем, что и то индукцией по получается, что