Московская МО-2020

zykov · Сообщение **zykov** » 02 апр 2021, 21:04

Да, для

сработала регулярность $a_{i+5}=a_i+a_{i+2}$ .
Вобщем та формула, что я предлагал, работает только для некоторых $k$

.
Для других можно другие формулы подобрать (на основе неприводимых многочленов).

А для других $n$

(не связанных со степенью 2) - вообще непонятно. Пробовал подобрать линейную рекурсию - не вышло.
Может там и нет регулярности, просто надо перебором искать.

zykov · Сообщение **zykov** » 03 апр 2021, 16:16

zykov писал(а):Source of the post Ian писал(а):
Source of the post так как приводим.

Там видимо должен быть многочлен .

Впрочем они оба неприводимые.
Они задают одну и ту же последовательность, только в разные стороны. Одна зеркально симметрична второй.
Если одна из последовательностей имеет максимальную длину, то и вторая тоже.

zykov · Сообщение **zykov** » 04 апр 2021, 13:34

Тут ещё такая тонкость, что многочлен должен быть не просто неприводимым, а должен быть примитивным многочленом.
Например при $k=4$

будет 3 неприводимых многочлена: $x^4+x^3+1$

,

. Из них только первые два генерируют максимальную последовательность.

zykov · Сообщение **zykov** » 04 апр 2021, 18:43

Кстати, с ростом длины будет уже больше одного решения.
Так при $k=5$

будет уже 6 примитивных многочленов (3 пары симметричных).
Многочлен $x^5+x^2+1$

даёт вектор

Код: Выбрать все

1   1   1   1   1   0   0   0   1   1   0   1   1   1   0   1   0   1   0   0   0   0   1   0   0   1   0   1   1   0   0

Многочлен

даёт вектор

Код: Выбрать все

1   1   1   1   1   0   0   1   0   0   1   1   0   0   0   0   1   0   1   1   0   1   0   1   0   0   0   1   1   1   0

Многочлен

даёт вектор

Код: Выбрать все

1   1   1   1   1   0   1   0   0   0   1   0   0   1   0   1   0   1   1   0   0   0   0   1   1   1   0   0   1   1   0

Все три вектора различны - не совмещаются сдвигом/отражением.

zykov · Сообщение **zykov** » 04 апр 2021, 21:26

Насчёт случая, когда это не степень двойки,

zykov писал(а):Source of the post Интересно, что во всех этих случаях () есть только один подходящий вектор

Попробовал посчитать $N=13$

(это длина вектора 27), так тут вектора с 13 совпадениями не нашлось. Максимум 11 совпадений.
Так что (если там нет ошибки) есть случаи, когда нет решения.

Зато следующий за ним - степень двойки, длина вектора 31 - как мы видели для $k=5$

даёт сразу 3 решения.

Портал Естественных Наук, версия 1.1