Разделы 
Дополнительно
Задача по математике - 2841
2019-05-06 
Дан произвольный набор из $N$ (где $N$ - полная степень двух: $N = 2^k$) чисел $A_1, A_2, \cdots, A_N$, каждое из которых равно +1 или -1. Исходя из этих чисел, следующим образом составляется новый набор чисел, каждое из которых также равно +1 или -1: $A_{1}^{\prime} = A_1A_2, A_{2}^{\prime} = A_2A_3, \cdots , A_{N-1}^{\prime} = A_{N-1}A_N, {A_N}^{\prime} = A_NA_1,$ затем по числам $A_{1}^{\prime}, A_{2}^{\prime}, \cdots, A_{N}^{\prime}$ точно так же находятся числа $A_{1}^{ \prime \prime}, A_{2}^{ \prime \prime} \cdots, A_{N}^{ \prime \prime}$, и т. д. Доказать, что в конце концов мы получим набор, состоящий из одних лишь чисел +1.
Решение:
Поскольку квадрат каждого из чисел $a_i$ (где $i = 1, 2, \cdots, N = 2^k$) равен единице, то первые три последовательности чисел имеют следующий вид:
$a_1, a_2, \cdots, a_{N-1}, a_N$;
$a_1a_2, a_2a_3, \cdots, a_{N-1}a_N, a_Na_1$;
$a_1a_2^2a_3 = a_1a_3, a_2a_3^2a_4 = a_2a_4, \cdots, a_{N-1}a_N^2a_1 = a_{N-1}a_1, a_Na_1^2a_2 = a_Na_2$;
таким образом, в 3-й последовательности все числа получаются умножением каждого из чисел последовательности на следующее за ним через одно (последовательность мы считаем «циклической», т. е. полагаем, что за числом $a_N$ следует $a_1$ затем $a_2$, и т. д.). Аналогично, еще через два шага мы будем иметь набор, получающийся из 3-го в точности так же, как 3-й получается из 1-го, т.е. набор
$(a_1a_3)(a_3a_5) = a_1a_5; (a_2a_4)(a_4a_6) = a_2a_6, \cdots, (a_Na_2)(a_2a_4) = a_Na_4$,
числа которого получаются из первого (циклического) набора перемножением чисел, следующих один за другим через 3. Еще через 4 шага мы получим набор, получающийся из 5-го в точности так же, 5-й набор получается из 1-го, т. е, набор
$(a_1a_5)(a_5a_9) = a_1a_9, (a_2a_6)(a_6a_{10}) = a_2a_{10}, \cdots, (a_Na_4)(a_4a_8) = a_Na_8$,
числа которого получаются из первоначального набора перемножением чисел, следующих один за другим через 7.
Вообще через $2^p$ шагов мы придем к набору
$a_1a_{2^p +1}, a_2a_{2^p +2}, \cdots, a_Na_{2^p}$,
получаемому из первоначального перемножением чисел, следующих один за другим через $2^p - 1$ чисел. Но отсюда следует, что через $2^k$ шагов мы придем к последовательности, получающейся из нашей (циклической!) последовательности перемножением чисел, следующих друг за другом через $2^k - 1 = N - 1$ номеров, т. е. к последовательности
$a_1a_1 = a_1^2 = 1, a_2a_2 = a_2^2 = 1, \cdots, a_Na_N = a_N^2 = 1$,
состоящей из одних единиц.
Дан произвольный набор из $N$ (где $N$ - полная степень двух: $N = 2^k$) чисел $A_1, A_2, \cdots, A_N$, каждое из которых равно +1 или -1. Исходя из этих чисел, следующим образом составляется новый набор чисел, каждое из которых также равно +1 или -1: $A_{1}^{\prime} = A_1A_2, A_{2}^{\prime} = A_2A_3, \cdots , A_{N-1}^{\prime} = A_{N-1}A_N, {A_N}^{\prime} = A_NA_1,$ затем по числам $A_{1}^{\prime}, A_{2}^{\prime}, \cdots, A_{N}^{\prime}$ точно так же находятся числа $A_{1}^{ \prime \prime}, A_{2}^{ \prime \prime} \cdots, A_{N}^{ \prime \prime}$, и т. д. Доказать, что в конце концов мы получим набор, состоящий из одних лишь чисел +1.
Решение:
Поскольку квадрат каждого из чисел $a_i$ (где $i = 1, 2, \cdots, N = 2^k$) равен единице, то первые три последовательности чисел имеют следующий вид:
$a_1, a_2, \cdots, a_{N-1}, a_N$;
$a_1a_2, a_2a_3, \cdots, a_{N-1}a_N, a_Na_1$;
$a_1a_2^2a_3 = a_1a_3, a_2a_3^2a_4 = a_2a_4, \cdots, a_{N-1}a_N^2a_1 = a_{N-1}a_1, a_Na_1^2a_2 = a_Na_2$;
таким образом, в 3-й последовательности все числа получаются умножением каждого из чисел последовательности на следующее за ним через одно (последовательность мы считаем «циклической», т. е. полагаем, что за числом $a_N$ следует $a_1$ затем $a_2$, и т. д.). Аналогично, еще через два шага мы будем иметь набор, получающийся из 3-го в точности так же, как 3-й получается из 1-го, т.е. набор
$(a_1a_3)(a_3a_5) = a_1a_5; (a_2a_4)(a_4a_6) = a_2a_6, \cdots, (a_Na_2)(a_2a_4) = a_Na_4$,
числа которого получаются из первого (циклического) набора перемножением чисел, следующих один за другим через 3. Еще через 4 шага мы получим набор, получающийся из 5-го в точности так же, 5-й набор получается из 1-го, т. е, набор
$(a_1a_5)(a_5a_9) = a_1a_9, (a_2a_6)(a_6a_{10}) = a_2a_{10}, \cdots, (a_Na_4)(a_4a_8) = a_Na_8$,
числа которого получаются из первоначального набора перемножением чисел, следующих один за другим через 7.
Вообще через $2^p$ шагов мы придем к набору
$a_1a_{2^p +1}, a_2a_{2^p +2}, \cdots, a_Na_{2^p}$,
получаемому из первоначального перемножением чисел, следующих один за другим через $2^p - 1$ чисел. Но отсюда следует, что через $2^k$ шагов мы придем к последовательности, получающейся из нашей (циклической!) последовательности перемножением чисел, следующих друг за другом через $2^k - 1 = N - 1$ номеров, т. е. к последовательности
$a_1a_1 = a_1^2 = 1, a_2a_2 = a_2^2 = 1, \cdots, a_Na_N = a_N^2 = 1$,
состоящей из одних единиц.
