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

zykov
Сообщений: 1060
Зарегистрирован: 06 янв 2016, 17:41

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

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

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

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

zykov
Сообщений: 1060
Зарегистрирован: 06 янв 2016, 17:41

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

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

zykov писал(а):Source of the post Ian писал(а):
Source of the post так как $x^7+x+1$ приводим.

Там видимо должен быть многочлен $x^7+x^6+1$.

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

zykov
Сообщений: 1060
Зарегистрирован: 06 янв 2016, 17:41

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

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

Тут ещё такая тонкость, что многочлен должен быть не просто неприводимым, а должен быть примитивным многочленом.
Например при $k=4$ будет 3 неприводимых многочлена: $x^4+x^3+1$, $x^4+x+1$, $x^4+x^3+x^2+x+1$. Из них только первые два генерируют максимальную последовательность.

zykov
Сообщений: 1060
Зарегистрирован: 06 янв 2016, 17:41

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

Сообщение 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

Многочлен $x^5+x^3+x^2+x+1$ даёт вектор

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

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

Многочлен $x^5+x^4+x^2+x+1$ даёт вектор

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

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
Сообщений: 1060
Зарегистрирован: 06 янв 2016, 17:41

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

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

Насчёт случая, когда это не степень двойки,
zykov писал(а):Source of the post Интересно, что во всех этих случаях ($N=1,3,5,7,9,11$) есть только один подходящий вектор

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

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


Вернуться в «Математика»

Кто сейчас на форуме

Количество пользователей, которые сейчас просматривают этот форум: нет зарегистрированных пользователей и 6 гостей