Итак, это завершающий пост про задачу из игры Sanitarium, где будет дано решение для случая восьми зацепов, а также рассмотрен более общий алгоритм решения для произвольного случая зацепов.
Итак, напомню, что конфигурацию крестовины и состояние зацепов я обозначаю многочленами, где степень при $x$ — порядковый номер зацепа или "усика" крестовины, а коэффициент обозначает состояние "открыт/закрыт" или конфигурацию крестовины (см первый пост). Сложение коэффициентов многочленов происходит по модулю $2$, а умножение многочленов — по модулю $x^8 + 1$, что обеспечивает "заворачивание" восьмой степени на нулевую, девятой на первую итд.
Напомню также, что ранее я получил частичное решение задачи, отыскав многочлены, имеющие обратный, и открывая зацепы последовательно по одному.
Теперь я подошел к задаче иначе. Интересный факт, что для любого $n \geq 1$ справедливо $x^n + 1 = (x+1)(\sum_{i=0}^{n-1}x^i)$ Последний сомножитель есть ни что иное, как многочлен, описывающий все зацепы в открытом состоянии. Далее, так как $x^8+1 = (x+1)^8 = (x+1)(\sum_{i=0}^{7}x^i)$, то $\sum_{i=0}^{7}x^i = (x+1)^7$.
Представим многочлен, описывающий нашу крестовину в виде $p(x) = f(x)(x+1)^n$, где $0 \leq n \leq 7$, где $f(x)$ — многочлен, не делящийся на $x+1$. Тогда, так как $f(x)$ и $x^8 + 1$ относительно простые, у $f(x)$ будет обратный элемент $f^{-1}(x)$. Теперь напишем многочлен $q(x) = f^{-1}(x)(x+1)^{7-n}$. Произведение $p(x)q(x) = f(x)f^{-1}(x) (x+1)^{n}(x+1)^{7-n} = (x+1)^{7}$ откроет в итоге все зацепы. Из выше сказанного можно сделать вывод, что для любой конфигурации крестовины можно найти комбинацию действий, открывающую все восемь зацепов.
Аналогично, решения существуют для любой крестовины в системе из $n$ зацепов, при котором выполняется равенство $x^n + 1 = (x+1)^n$. Легко видеть, что $n=2^k$, где $k = 0,1,2,\cdots$
Используя ту же схему доказательства, рассмотрим случай с $n$ зацепами, где $n$ — нечётное число. Тогда очевидно, что многочлен $\sum_{i=0}^{n-1}x^i$, соответствующий всем открытым зацепам, не делится на $x+1$. Например, для $n=5$ $x^4+x^3+x^2+x+1 = x^{3}(x+1) + x(x+1) + 1 = (x+1)(x+x^3)+1$ не делится на $x+1$. Тогда для крестовины $p(x) = (x+1)f(x)$, где $f(x)$ — любой другой многочлен, не будет существовать решения, так как многочлен $x+1$ не имеет обратного. Простейший пример задачи, не имеющей решения, приведен на картинке:
В качестве упражнения предлагаю читателю доказать, что для оставшихся случаев (кол-во зацепов $n$ чётное, но не степень двойки) тоже есть не имеющие решения конфигурации крестовины.
Итак, напомню, что конфигурацию крестовины и состояние зацепов я обозначаю многочленами, где степень при $x$ — порядковый номер зацепа или "усика" крестовины, а коэффициент обозначает состояние "открыт/закрыт" или конфигурацию крестовины (см первый пост). Сложение коэффициентов многочленов происходит по модулю $2$, а умножение многочленов — по модулю $x^8 + 1$, что обеспечивает "заворачивание" восьмой степени на нулевую, девятой на первую итд.
Напомню также, что ранее я получил частичное решение задачи, отыскав многочлены, имеющие обратный, и открывая зацепы последовательно по одному.
Теперь я подошел к задаче иначе. Интересный факт, что для любого $n \geq 1$ справедливо $x^n + 1 = (x+1)(\sum_{i=0}^{n-1}x^i)$ Последний сомножитель есть ни что иное, как многочлен, описывающий все зацепы в открытом состоянии. Далее, так как $x^8+1 = (x+1)^8 = (x+1)(\sum_{i=0}^{7}x^i)$, то $\sum_{i=0}^{7}x^i = (x+1)^7$.
Представим многочлен, описывающий нашу крестовину в виде $p(x) = f(x)(x+1)^n$, где $0 \leq n \leq 7$, где $f(x)$ — многочлен, не делящийся на $x+1$. Тогда, так как $f(x)$ и $x^8 + 1$ относительно простые, у $f(x)$ будет обратный элемент $f^{-1}(x)$. Теперь напишем многочлен $q(x) = f^{-1}(x)(x+1)^{7-n}$. Произведение $p(x)q(x) = f(x)f^{-1}(x) (x+1)^{n}(x+1)^{7-n} = (x+1)^{7}$ откроет в итоге все зацепы. Из выше сказанного можно сделать вывод, что для любой конфигурации крестовины можно найти комбинацию действий, открывающую все восемь зацепов.
Аналогично, решения существуют для любой крестовины в системе из $n$ зацепов, при котором выполняется равенство $x^n + 1 = (x+1)^n$. Легко видеть, что $n=2^k$, где $k = 0,1,2,\cdots$
Используя ту же схему доказательства, рассмотрим случай с $n$ зацепами, где $n$ — нечётное число. Тогда очевидно, что многочлен $\sum_{i=0}^{n-1}x^i$, соответствующий всем открытым зацепам, не делится на $x+1$. Например, для $n=5$ $x^4+x^3+x^2+x+1 = x^{3}(x+1) + x(x+1) + 1 = (x+1)(x+x^3)+1$ не делится на $x+1$. Тогда для крестовины $p(x) = (x+1)f(x)$, где $f(x)$ — любой другой многочлен, не будет существовать решения, так как многочлен $x+1$ не имеет обратного. Простейший пример задачи, не имеющей решения, приведен на картинке:
Comments
Post a Comment