Частичное решение задачи в Sanitarium

В предыдущем посте я рассмотрел задачу из игры Sanitarium, связанную с открытием зацепов, удерживающих камень. Я пришел к выводу, что задача частично сводится к нахождению многочленов $p(x)$, имеющих обратный по отношению к операции умножения, т.е. $p(x)q(x)=1$ на кольце $F_{2}[x]/(x^8+1)$. Был получен результат, что не каждый многочлен имеет обратный, так как генерирующий многочлен факторкольца разлагается на множители: $(x^8+1) = (x+1)^8$. Логично искать обратимые многочлены среди относительно простых по отношению к $x^8+1$, т.е. тех, которые не делятся на $x+1$. Проверим несколько многочленов:

• $1$ — крестовина из одного элемента, тривиальное решение.
• $x$ — аналогично.
• $x+1$ — делится на $x+1$.
• $x^2$ — опять крестовина из одного элемента.
• $x^2+1$ — делится на $x+1$.
• $x^2+x+1$ — не тривиальное решение и не делится на $x+1$ — наш клиент!

Написав на своем любимом лиспике простую программку, я подобрал обратный многочлен $q(x) = x^7 + x^5 + x^4 + x^2 + x$. Как это работает? На картинке представлены шаги умножения многочлена $p(x) = x^2 + x + 1$ последовательно на все члены $q(x)$

Мы видим, что во всех положениях, соответствующих степеням $n \neq 0$ крестовина побывала ровно 2 раза, соответственно, оставив зацепы в своём изначальном положении ("закрыто"), а в положении, соответствующем степени $0$ — один раз, открыв этот зацеп. Повторяя процедуру для крестовины, смещенной на 1 позицию вправо, откроем второй зацеп и так далее.

Теперь что,  если число зацепов будет не восемь, а, например, 5 или любое другое число, в том числе простое? Можно проверить, что многочлен $x^n + 1$ делится на $x+1$ при любом $n \geq 1$, так что ни одно из колец $F_{2}[x]/(x^n+1)$ не будет полем, то есть будут многочлены не равные $0$, для которых обратного элемента не будет и этот алгоритм не сработает. Опять же нужно будет искать многочлены, относительно простые с $x^n+1$.

Отсутствие обратного многочлена не означает, что задача не имеет решения для данной конфигурации крестовины. Например для многочлена $p(x) = x^4 + 1$ (одна "стрелка" крестовины смотрит вверх, другая — вниз) решение очевидно — нужно нажимать на кнопку и поворачивать крестовину на одну позицию 3 раза, пока не откроются все зацепы. Данный случай требует отдельного анализа.