Прикладная математика и прочее веселье

Итак, это завершающий пост про задачу из игры Sanitarium, где будет дано решение для случая восьми зацепов, а также рассмотрен более общий алгоритм решения для произвольного случая зацепов. Итак, напомню, что конфигурацию крестовины и состояние зацепов я обозначаю многочленами, где степень при $x$ — порядковый номер зацепа или "усика" крестовины, а коэффициент обозначает состояние "открыт/закрыт" или конфигурацию крестовины (см первый пост ). Сложение коэффициентов многочленов происходит по модулю $2$, а умножение многочленов — по модулю $x^8 + 1$, что обеспечивает "заворачивание" восьмой степени на нулевую, девятой на первую итд. Напомню также, что ранее я получил частичное решение задачи, отыскав многочлены, имеющие обратный, и открывая зацепы последовательно по одному. Теперь я подошел к задаче иначе. Интересный факт, что для любого $n \geq 1$ справедливо $x^n + 1 = (x+1)(\sum_{i=0}^{n-1}x^i)$ Последний сомножитель есть ни что иное, как многочлен

В предыдущем посте я рассмотрел задачу из игры 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$. Как это работает? Н

Sanitarium — невероятно интересный (по мнению автора) квест 1998 года выпуска про учёного-микробиолога по имени Макс, попавшего в сумасшедший дом после потери памяти в результате автомобильной аварии. По ходу игры Макс перемещается между параллельными мирами, придуманными силой воображения… Одним словом, лучше поиграть, а не читать спойлеры. В части игры "Лаборатория" (7 часть) представлена очень интересная задача. Нужно открыть восемь круговых зацепов, охватывающих камень, чтобы тот упал. Зацепами управляет треугольная крестовина (на самом деле, 4-х угольная, но один конец там поломан и не влияет на зацепы) на пульте управления. Крестовину можно повернуть вокруг оси на одну позицию в любую сторону. При нажатии на кнопку, зацепы, соответствующие положению крестовины, меняют своё состояние (запертый зацеп отпирается, открытый — закрывается). Вот скриншот для ясности: Цель оригинальной головоломки, как я сказал, — открыть все зацепы. Я предлагаю усложнённый вариант —