Skip to main content

Частичное решение задачи в 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 раза, пока не откроются все зацепы. Данный случай требует отдельного анализа.

Comments

Post a Comment

Popular posts from this blog

Гладкая сшивка кусочно-постоянной функции.

Накануне мне понадобилось найти гладкую функцию, определенную на $\textbf{R}[a,c]$, равную единице на одном отрезке числовой оси, скажем, $[a, b-\epsilon]$ и нулю на другом, скажем $[b+\epsilon, c]$. Для того, чтобы гладко склеить эти два кусочка, я решил найти монотонно убывающий многочлен $f(x)$, равный $f(0) = 1$ и $f(1) = 0$, а потом "вставить" его в отрезок $[b-\epsilon, b+\epsilon]$. Для гладкости сшивки должны выполняться условия $f'(0) = f'(1) = 0$. Я решил пойти далее и положить $f^{(n)}(0) = f^{(n)}(1) = 0$ для всех $n = 1,2,\cdots,N$. То есть первые N производных должны быть равны нулю в т. $x = 0$ и $x = 1$. Понятно, что это легко сделать при наперед известном N, но как найти общую формулу? Я некоторое время промучился над этой задачей, пока не решил её следующим способом. Пусть искомая функция $f(x) = 1 + x^{N+1}L_{1}(x)$, где $L_{1}(x)$ — некий многочлен. Тогда у нас выполняется условие $f(0) = 1$ и $f^{(n)}(0) = 0$ (так как первая производная будет...
Post a Comment
Read more

На что влияет размер (глубина) семпла?

В этом посте я разберу ещё одну характеристику представления аудио на компьютере — размер или глубину семпла. В теореме Шеннона, с которой мы ознакомились в первом посте, сказано, что семплы нужно брать с определенной частотой, чтобы восстановить исходный сигнал. Однако, в ней ничего не сказано о том, сколько памяти компьютера нужно выделить на один семпл. По сути  ней семплы — это обычные вещественные числа. В компьютере же семплы чаще всего представляются целыми числами в диапазоне от $-2^{n-1}$ до $2^{n-1}-1$ (целые числа со знаком), где $n$ — количество бит на один семпл (bps, bits per sample). С количеством бит на семпл связана другая величина — динамический диапазон (или отношение сигнал-шум, что в данном случае то же самое). Он измеряется в децибелах определяется так: $DR = 20 \lg (2^{n}) \approx 6 n$ Динамический диапазон показывает логарифм отношения самого сильного сигнала к самому слабому. Теперь, что будет, если мы выберем $n$ маленьким? Если взять синусоидальную ...
Post a Comment
Read more

Dithering (часть 2)

В начале поста хочу рассказать о некоторой неточности, совершенной мной в предыдущем посте. А именно, "треугольно" распределенный шум берут в диапазоне $[-2\Delta, 2\Delta]$ (при этом мощность его будет $W = 2\Delta^{2}/3$). Придумали его не для того, чтобы звучать тише, а чтобы сделать первый и второй условные моменты функции ошибки $E[\epsilon^{m}|x] = \int_{-\infty}^{\infty} \epsilon^{m}p_{\epsilon|x}(\epsilon, x) d\epsilon$ независимыми от $x$. Привожу цитату из статьи  Quantization and Dither: A Theoretical Survey авторов Stanley P.Lipshitz, Robert A. Wannamaker и John Vanderkooy: Now consider a triangular-pdf dither of 2-LSB peak-to-peak amplitude resulting from the sum of two independent rectangular-pdf noises $v_{1}$ and $v_{2}$, each of 1-LSB peak-to-peak amplitude (...) (...) so this dither renders both the first and second moments of the total error independent of $x$. The second moment of the total error is a constant $\Delta^{2}/4$ for all inputs, (...) Ну ...
Post a Comment
Read more