Ещё одна формулировка задачи М574:
Найдите последовательность $e_1\lt e_2\lt\ldots\lt e_t$ натуральных чисел такую, что каждое число от $1$ до $e_t-e_1$ представляется в виде разности $e_j-e_i$ некоторых из этих чисел нечётным числом способов.
Первое решение. Легко придумать такую последовательность из четырёх чисел: $A_1=1101$. Чтобы построить нужную последовательность из 25 чисел, мы трижды используем $A_1$, причём разделяем $A_1$ нулями так:
$$
A_2=1101\,000\,1101\,0000000000\,1101.
$$
Такое построение можно продолжить и далее: если последовательность $A=(a_1,a_2,\ldots,a_n)$ удовлетворяет условию задачи, то и последовательность
$$
B=(\underbrace{A}_{n}\underbrace{00\ldots0}_{n\smash{-1}}\underbrace{A}_{n}\underbrace{00\ldots0}_{\smash3n\smash{-2}}\underbrace{A}_{n})=(b_1,b_2,\ldots,b_{7n-3}),
$$
состоящая из трёх наборов $A$ и двух наборов нулей между ними, также ему удовлетворяет.
Докажем более общий факт: вместе с последовательностями $A=(a_1,a_2,\ldots,a_n)$ и $C=(c_1,c_2,\ldots,c_m)$ удовлетворяет условию задачи и последовательность $B$ длины $(2n-1)(m-1)+n$ из $m$ «блоков»:
$$
\colsep{0pt}{\begin{array}{rlllll}
B=(&a_1c_1,{}&a_2c_1,{}&\ldots,{}&a_nc_1,{}&\overbrace{0,0,\ldots,0}^{n-1},\\
&a_1c_2,{}&a_2c_2,{}&\ldots,{}&a_nc_2,{}&0,0,\ldots,0,\\
&\mathrlap{~.~.~.~.~.~.~.~.~.~.~.~.~.~.~.~.~.~.~.~.~.~.~.~.~.~.~.~.}\\
&a_1c_{m-1},{}&a_2c_{m-1},{}&\ldots,{}&a_nc_{m-1},{}&0,0,\ldots,0,\\
&a_1c_m,{}&a_2c_m,{}&\ldots,{}&a_nc_m);
\end{array}}
$$
здесь $j$-й блок повторяет последовательность $A$, если $c_j=1$, и нулевой, если $c_j=0$.
Выпишем подряд $l$-значные числа семиричной системы от $\underbrace{11\ldots1}_l$ до $\underbrace{44\ldots4}_l$ $\Big($их будет $\dfrac{7^l+1}2\Big)$. Против тех чисел, в записи которых встречаются только цифры 1, 2 и 4, поставим $1$, а против остальных — $0$. Получим последовательность $A_l$, удовлетворяющую условию. Например, при $l=2$ получится $A_2{:}$
$$
\def\r#1{\enspace\textcolor{red}{#1}}
\colsep{0pt}{\begin{array}{rcrcrcrc}
&&\quad20&\r0&\quad30&\r0&\quad40&\r0\\
11&\r1&21&\r1&31&\r0&41&\r1\\
12&\r1&22&\r1&32&\r0&42&\r1\\
13&\r0&23&\r0&33&\r0&43&\r0\\
14&\r1&24&\r1&34&\r0&44&\r1\\
15&\r0&25&\r0&35&\r0\\
16&\r0&26&\r0&36&\r0
\end{array}}
$$
Пусть целое $k=(2n-1)q+r$, где $q=0$, $r=0$, 1, $\ldots$, $n-1$ или $-n\lt r\lt n$, $0\lt q\lt m$ ($q$ и $r$ — целые). Тогда при сдвиге последовательности $B$ на $k$ мест $j$-й блок $(a_1c_j,a_2c_j,\ldots,a_nc_j)$ будет пересекаться только с ($j+q$)-м блоком исходной последовательности, причём со сдвигом на $r$ единиц в индексах $a_i$; поэтому сумма $$
S_k(B)=b_1b_{k+1}+b_2b_{k+2}+b_3b_{k+3}+\ldots
$$
представляется в виде произведения $$(c_1c_{j+1}+c_2c_{j+2}+\ldots)(a_1a_{1+|r|}+a_2a_{2+|r|}+\ldots)=S_j(C)\,S_{|r|}(A)
$$
и, следовательно, является нечётным числом для любого целого $k$ от 0 до $(2n-1)(m-1)+(n-1)$. При $C=(1,1,0,1)$ получаем нужный нам частный случай.
Таким образом, по набору длины $n$, удовлетворяющему условию задачи, можно построить набор длины $7n-3$, также удовлетворяющий этому условию. Начиная с набора длины 1, состоящего из одной единицы, мы получим бесконечную серию таких наборов: $A_0$, $A_1$, $A_2$, $A_3$, $\ldots$, $A_l$, $\ldots$ Их длины будут равны 4, 25, 172, 1201, $\ldots$, $\dfrac{7^l+1}2$, $\ldots$
На полях показано, как, используя семиричную систему счисления, можно сразу выписать последовательность $A_l$, для любого $l=0$, 1, 2, $\ldots$
Второе решение задачи б). Определим семейство последовательностей $\{D_n\}$ по индукции следующим образом: $D_0=(1)$ и если $D_n=(d_1,d_2,d_3,\ldots,d_r)$, то $$
D_{n+1}=(1,0,1,d_1,1,0,1,d_2,1,0,1,d_3,\ldots,1,0,1,d_{r-1},1,0,1,d_r).
$$
(Например, $D_1=(1,0,1,1)$, $D_2=(1,0,1,1,1,0,1,0,1,0,1,1,1,0,1,1)$.)
Доказать, что $D_n$ удовлетворяет условию задачи, можно по индукции. При этом нужно рассмотреть отдельно четыре случая: $k=4l$, $k=4l+1$, $k=4l+2$, $k=4l+3$, причём для разбора случаев $k=4l+1$ и $k=4l+3$ нужно предварительно доказать (тоже индукцией) следующую лемму:
Каждая последовательность $D_n=(d_1,d_2,d_3,\ldots,d_r)$ симметрична: $d_j=d_{r-j}$ для всех $1\le j\le r-1$, а $d_r=1$.
Рассмотрим, например, случай $k=4l+1$. Написав под $D_{n+1}$ эту же последовательность, сдвинутую на $4l+1$ членов, легко найти
$$
\begin{gather*}
S_k(D_{n+1})=(d_{l+1}d_1+d_{l+2}+d_2+\ldots+d_{r-1}+d_{r-l-1})+d_r=\\
=(d_1+d_2+\ldots+d_{r-l-1})+(d_{l+1}+d_{l+2}+\ldots+d_{r-1})+d_r,
\end{gather*}
$$
а это число нечётное по лемме о симметрии $D_n$. Для $k=4l+3$ доказательство аналогично предыдущему, а случаи $k=4l$ и $k=4l+2$ более просты.
К сожалению, этот метод не позволяет получить из любой последовательности длины $n$ последовательность длины $4n$. Для его применения необходимо соблюдение условий леммы о симметрии, что бывает, конечно, далеко не всегда.
$$\colsep{2pt}{\begin{array}{c|rrrrrrrrr}
n&~4&12&16&24&25&36&37&40&45\\[2pt]\hline\\[-9pt]
2n{-}1&7&23&31&47&49&71&73&79&89
\end{array}}$$
Последовательности для $n=12$ и $n=24$ (соответственно, чёрная и красная строчки):
$$
\def\r#1{\textcolor{red}{\mathclap{#1}}}
\def\0{\r0}\def\1{\r1}
\colsep{2pt}{\begin{array}{ccccccccccccccccccc}
1&&1&&0&&0&&0&&1&&1&&1&&0&&1&&0&&1\\
\1&\1&\1&\1&\0&\1&\1&\1&\0&\1&\1&\0&\1&\1&\1&\0&\0&\0&\1&\1&\0&\0&\0&\1\\
\end{array}}
$$
При первом из описанных способов построения бесконечной серии последовательностей $A_0$, $A_1$, $A_2$, $\ldots$, удовлетворяющих условию задачи, их длины равны $\dfrac{7^l+1}2$ ($l=0$, 1, 2, $\ldots$). Второй способ даёт последовательности с длинами $4^l$ ($l=0$, 1, 2, $\ldots$). Какие же значения может принимать длина последовательности, удовлетворяющей условию задачи? Оказывается, те значения $n$, для которых $2n-1$ является делителем числа $2^k-1$ при некотором нечётном $k$. Это показали в 1976 году Ф. Дж. МакВильямс и А. И. Одлизко. Такие $2n-1$ в пределах сотни и соответствующие последовательности для $n=12$ и $n=24$ указаны на полях. Легко проверить, что длины построенных нами последовательностей удовлетворяют этому критерию: если $n=\dfrac{7^l+1}2$, $l\ge1$, то $2n-1$ делит $2^{3\cdot7^{l-1}}-1$ (докажите!), а если $n=4^l$, то $2n-1$ делит $2^{2l+1}-1$. Примеры последовательностей достаточно строить для тех $n$, удовлетворяющих критерию, у которых $2n-1$ — простое (подумайте, как получить из них остальные). Но для более глубокого анализа задачи и доказательства общего результата нужно перейти на новый, неэлементарный язык, типичный для алгебраической теории кодирования: последовательность $a_1$, $a_2$, $\ldots$, $a_n$ нулей и единиц pacсматривать как многочлен $A(x)=a_1+a_2x+\ldots+a_nx^{n-1}$ с коэффициентами из поля $F_2=\{0,1\}$ (в этом поле $1+1=0$), удовлетворяющую такому условию (*): в разложении выражения $A(x)\,A(x^{-1})$ по степеням $x$ все коэффициенты при $x^{-(n-1)}$, $x^{-(n-2)}$, $\ldots$, $x^{n-2}$, $x^{n-1}$ нечётны.
Новый вариант задачи М574 получится, если располагать последовательности из 0 и 1 на окружности и требовать, чтобы при любом $k$ сумма попарных произведений членов, отстоящих на $k$, была нечётной. Если вам удастся получить результаты по этой задаче, напишите нам об этом.
Наши два решения на этом языке коротко формулируются так:
- вместе с многочленами $A(x)$ степени $\dfrac{p-1}2$ и $C(x)$ степени $\dfrac{q-1}2$ условию (*) удовлетворяет также многочлен $A(x)\cdot C(x^p)=B(x)$ степени $\dfrac{pq-1}2$;
- в последовательности
$$
D_1(x)=1+x^2+x^3,\quad D_{n+1}(x)=\dfrac{1-x^{4^n}}{1-x^2}+D_n(x^4)
$$
все многочлены удовлетворяют условию (*).
