Разделы 
Дополнительно
Задача по математике - 3801
2019-06-16 
Конечная последовательность $a_1, a_2, \cdots, a_n$ из чисел 0 и 1 должна удовлетворять следующему условию: для любого целого $k$ от 0 до $n - 1$ сумма
$a_1a_{k+1} + a_2a_{k+2} + \cdots + a_{n-k}a_n$
является нечетным числом.
а) Придумайте такую последовательность для $n = 25$.
б) Докажите, что такая последовательность существует для некоторого $n > 1000$.
Решение:
Указанную в условии задачи величину
$p_k = a_1a_{k+1} + a_2a_{k+2} + \cdots + a_{n-k}a_n$
удобно подсчитывать так: последовательность $A_n = (a_1, a_2, \cdots, a_n)$ из 0 и 1 подписывается сама под собой со сдвигом на $k$ разрядов; при этом $p_k = p_k(A_n)$ - число разрядов, в которых в обеих строках стоят единицы.
Последовательность $A_n$ длины $n$ удовлетворяет условию задачи, если все $p_k(A_n)$ при $0 \leq к \leq n - 1$ нечетны.
Следующая конструкция позволяет по двум таким последовательностям $A_m$ и $A_n$ построить $A_l = A_n \bigsqcup A_m$ длины $l = (2m - 1)n - (m - 1) = 2mn - m + 1$. Заменим каждую 1 в $A_n$ на блок $A_m \underbrace{0 \cdots 0}_{m - 1}$ из $2m - 1$ цифр, каждый 0 в $A_n$ - на блок из $2m - 1$ нулей, а последние $m - 1$ нулей отбросим. При подсчете pk для At указанным выше способом при любом сдвиге k каждый блок $A_m$ в верхней строке задевает лишь один блок $A_m$ в нижней; если $k = (2m-l)q + r$ или $k = (2 m - 1)q - r$, где $0 \leq r \leq m - 1$, $0 \leq q \leq n - 1$, то $p_k(A_l) = p_q(A_n) \cdot p_r(A_m)$, поскольку ровно $p_q(A_n)$ пар блоков $A_m$ задевают друг друга и при этом они сдвинуты на $r$ разрядов; отсюда ясно, что построенная последовательность $A_l = A_n \bigsqcup A_m$ удовлетворяет условию задачи вместе с $A_n$ и $A_m$.
Эта конструкция позволяет из $A_4 = 1101$ изготовить ответ $A_{25} = A_4 \bigsqcup A_4$ к пункту а):
$A_{25} = \underbrace{1101000} \underbrace{1101000} \underbrace{0000000} \underbrace{1101}$.
Далее, $A_{25} \bigsqcup A_{25}$ имеет уже $2 \cdot 25^2 - 50+ 1 = 1201$ - более 1000 цифр, что и требуется в пункте б),
Конечная последовательность $a_1, a_2, \cdots, a_n$ из чисел 0 и 1 должна удовлетворять следующему условию: для любого целого $k$ от 0 до $n - 1$ сумма
$a_1a_{k+1} + a_2a_{k+2} + \cdots + a_{n-k}a_n$
является нечетным числом.
а) Придумайте такую последовательность для $n = 25$.
б) Докажите, что такая последовательность существует для некоторого $n > 1000$.
Решение:
Указанную в условии задачи величину
$p_k = a_1a_{k+1} + a_2a_{k+2} + \cdots + a_{n-k}a_n$
удобно подсчитывать так: последовательность $A_n = (a_1, a_2, \cdots, a_n)$ из 0 и 1 подписывается сама под собой со сдвигом на $k$ разрядов; при этом $p_k = p_k(A_n)$ - число разрядов, в которых в обеих строках стоят единицы.
Последовательность $A_n$ длины $n$ удовлетворяет условию задачи, если все $p_k(A_n)$ при $0 \leq к \leq n - 1$ нечетны.
Следующая конструкция позволяет по двум таким последовательностям $A_m$ и $A_n$ построить $A_l = A_n \bigsqcup A_m$ длины $l = (2m - 1)n - (m - 1) = 2mn - m + 1$. Заменим каждую 1 в $A_n$ на блок $A_m \underbrace{0 \cdots 0}_{m - 1}$ из $2m - 1$ цифр, каждый 0 в $A_n$ - на блок из $2m - 1$ нулей, а последние $m - 1$ нулей отбросим. При подсчете pk для At указанным выше способом при любом сдвиге k каждый блок $A_m$ в верхней строке задевает лишь один блок $A_m$ в нижней; если $k = (2m-l)q + r$ или $k = (2 m - 1)q - r$, где $0 \leq r \leq m - 1$, $0 \leq q \leq n - 1$, то $p_k(A_l) = p_q(A_n) \cdot p_r(A_m)$, поскольку ровно $p_q(A_n)$ пар блоков $A_m$ задевают друг друга и при этом они сдвинуты на $r$ разрядов; отсюда ясно, что построенная последовательность $A_l = A_n \bigsqcup A_m$ удовлетворяет условию задачи вместе с $A_n$ и $A_m$.
Эта конструкция позволяет из $A_4 = 1101$ изготовить ответ $A_{25} = A_4 \bigsqcup A_4$ к пункту а):
$A_{25} = \underbrace{1101000} \underbrace{1101000} \underbrace{0000000} \underbrace{1101}$.
Далее, $A_{25} \bigsqcup A_{25}$ имеет уже $2 \cdot 25^2 - 50+ 1 = 1201$ - более 1000 цифр, что и требуется в пункте б),
