Задача про лампы.

[Бином]

Пусть n > 1 – целое число. По окружности расположено n ламп L0, … ,Ln – 1. Каждая лампа может быть в состоянии «включена» или «выключена». Последовательность шагов S0,S1, … ,Si, … определена следующим образом. Шаг Sj влияет только на состояние лампы Lj (и не влияет на состояние остальных ламп) так что, если Lj – 1 включена, то Sj изменяет состояние лампы Lj (то есть, если Lj была включена, то станет выключена и наоборот). Если Lj – 1 выключена, то Sj ничего не меняет. Лампы пронумерованы по модулю n (т.е. Ln = L0 и т.д.)

Первоначально все лампы включены. Доказать, что


а) Существует натуральное M(n) такое, что после M(n) все лампы будут включены.


б) Если n – число вида 2k, то после n^2 -1 шагов все лампы будут включены.

в) Если n – число вида 2k + 1, то после n^2 -n + 1 шагов все лампы будут включены.

[Kid Kool]

Каждой конфигурации ламп на окружности соответствует n-битное число, у которого k-ый разряд равен 1, если соответствующая лампа выключена. Поскольку каждая конфигурация однозначно определена предыдущей, и количество конфигураций конечно, то последовательность периодична. Т.к. первый элемент ее равен 0, то 0 также равен и первый элемент второго периода. Т.е. пункт а) доказан.

[maxal]

Kid Kool писал(а):

Каждой конфигурации ламп на окружности соответствует n-битное число, у которого k-ый разряд равен 1, если соответствующая лампа выключена. Поскольку каждая конфигурация однозначно определена предыдущей,

Это неверно. Есть еще зависимость от номера шага.

Kid Kool писал(а):

и количество конфигураций конечно, то последовательность периодична. Т.к. первый элемент ее равен 0, то 0 также равен и первый элемент второго периода.

Это теперь ниоткуда не следует.

Добавлено спустя 1 минуту 57 секунд:

Бином, на форуме для записи формул используется $\LaTeX$ нотация и тэг [math]. Отредактируйте ваше сообщение в соответствии с правилами!

[Руст]

Выключенное сосстояние лучше обозначать 0, так как в этом случае не меняется состояние следующей лампы $x_j^{(k)}=x_j^{(k-1)}+x_{j-1}^{(k-1)},k=j\mod n$, здесь $x_j^{(k)}$ состояние j - ой лампочки после k-ого шага, сложения всюду по модулю 2, индексы по модулю n.
Лучше определить рекурентно последовательность $y_k$ число $x_j^{(k)}, j=k\mod n$ продолжая цифры после n-1 , битов до бесконечности по формуле: $y_k=y_{k-1}+y_{k-n}$ с начальными условиями $y_0=y_1=...,y_{n-1}=1$ через характеристический многочлен $x^n-x^{n-1}-1=0$ легко получается указанный период.

[Kid Kool]

maxal писал(а):

Это неверно. Есть еще зависимость от номера шага.

Замечание принимается. Тогда допишем к нашему двоичному числу еще и номер шага по модулю n. Тогда зависимость станет однозначной.

[maxal]

Руст писал(а):

Лучше определить рекурентно последовательность $y_k$ число $x_j^{(k)}, j=k\mod n$ продолжая цифры после n-1 , битов до бесконечности по формуле: $y_k=y_{k-1}+y_{k-n}$ с начальными условиями $y_0=y_1=...,y_{n-1}=1$ через характеристический многочлен $x^n-x^{n-1}-1=0$ легко получается указанный период.

Ну точно, а я голову ломал, что эта задача мне напоминает. Как раз недавно периоды таких полиномов вычислял. :)

[Руст]

На самом деле минимальным периодом является такое T, что многочлен $x^n+x+1|x^T+1$ над $F_2$ (на знаки можно не обращать внимания, да и $x^n+x^{n-1}+1$ можно заменить на возвратно симметричный, так как $x^T+1$ всегда возвратно симметричный). Только указанные автором периоды точны только в случае $n=2^k$ и $n=2^k-1$. В общем случае надо ещё считать.

[maxal]

Руст писал(а):

Только указанные автором периоды точны только в случае $n=2^k$ и $n=2^k-1$. В общем случае надо ещё считать.

Даже если разрешить $n$ быть кратным периоду, то указанные формулы начинают врать уже для $n=6$.
Так, при $n=6$ период $x^n + x + 1$ над GF(2) равен A046932(6)=63 и он не делит $n^2-1=35$, как того требует условие б).

Добавлено спустя 7 минут 42 секунды:

Хехе. А это оказывается Problem 6 с IMO 1993, и там в формулировке $2^k$ вместо $2k$ и $2^k+1$ вместо $2k+1$ соответственно.

Еще статейка такая по этой задачке есть:
Laurent Bartholdi, Lamps, Factorizations and Finite Fields.

[Руст]

$2^k-1$ я написал соображая в уме, на самом деле $2^k+1$, действительно
$x^T+1=x(x+1)^{n-1}+1\mod x^n+x+1 =x^n+x+1=0$. Тем не менее эта формула $T=n^2-n+1$ работает и для $n=3=2^2-1$ (возможно это подтолкнуло меня изменить знак). Для $n=2^k$ получаем $x^{n^2}+x=(x+1)^n+x=x^n+x+1=0$, т.е $x^{n^2-1}+1=0$.
В общем случае легко доказать, что T является делителем $Lcm(2^{k_i}-1)$, где $k_i$ степени при разложении $x^n+x+1=\prod_i f_i(x)$ над $F_2$ неприводимых многочленов $f_i$.
А для вышеуказанных значений n $3,2^k,2^k+1$ легко показать, что это действительно минимальный период.

[RIP]

Руст писал(а):

Тем не менее эта формула $T=n^2-n+1$ работает и для $n=3=2^2-1$ (возможно это подтолкнуло меня изменить знак).

Просто $3=2^1+1$.