Итак, это завершающий пост про задачу из игры 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