Израильский суперфинал

peregoudov · Сообщение **peregoudov** » 04 окт 2019, 23:57

Мне кажется, рассуждения можно упростить, если вместо $a_k$

ввести их частичные суммы $S_k=\sum_{i=1}^k a_i$ . Условия задачи тогда переписываются в виде $S_{2k+1\mod n}=S_k$ , $k=1$

, ...

,

. И дальше, наверное, нужно какие-то соотношения по модулю n между индексами рассматривать. Если выписывать матрицу, то в ней, помимо главной диагонали из единиц, еще две "диагонали" вдвое меньшего наклона из -1. А можно еще рисовать графы.

peregoudov · Сообщение **peregoudov** » 06 окт 2019, 19:13

И нам надо изучить свойства отображения $k\to p=2k+1\mod n$ .

Для нечетного $n$

это перестановка, потому что разные $k$

отображаются в разные $p$

. Действительно $k_1$

и

могут отобразиться в одно и то же $p$

, только если $2k_1+1=2k_2+1\mod n$ , что при нечетных $n$

невозможно.

Всегда существует $k$

, отображающееся само в себя. Оно определяется уравнением $2k+1=k+n$

и равно

.

Из сказанного следует, что в перестановке при нечетных $n$

есть цикл единичной длины $(n-1)$

, соответствующую переменную можно взять ненулевой. Это воспроизводит уже полученное выше решение для нечетных $n$

.

Если

с нечетным $m$

, то существует последовательность отображения индексов

$m-1\to 2m-1\to\ldots\to2^lm-1=n-1.$

Последний индекс отображается сам в себя, а получить первый член отображением невозможно, так как $2k+1\mod n$ нечетно, а $m-1$

четно. Таким образом, существует отдельная ветвь графа, не содержащая индекса 1, соответствующие переменные можно взять ненулевыми. Это воспроизводит решение Ian'а для $n$

, содержащих нечетный множитель.

Наконец, для четных $n=2m$

замечаем, что четные индексы отображаются в нечетные, а нечетные --- сами в себя, поэтому достаточно рассмотреть отображение только нечетных индексов, подставляя $p=2q+1$

и

имеем $q=2j+1\mod m$ . Получили ту же задачу, только с вдвое меньшим $n$

. Для

можно продолжить, сведя к $n=2$

, для которого отсутствие нетривиальных решений проверяется непосредственно. Для $n=2^lm$

можно свести к нечетному $n=m$

, для которого существование нетривиального решения уже доказана.

Ian · Сообщение **Ian** » 07 окт 2019, 09:10

Действительно, уравнения задают присваивания

S_k друг другу (а

S_1 нулю) по орбитам отображения

k\to (2k+1)\mod n и при

n=2^l надо доказать, что в присваивания будут вовлечены все возможные остатки k=0,1...(n-1). Каждый индекс k запишем в двоичной системе

l-значным числом(n и 0 отождествляем), отображение сдвигает знаки влево (с потерей самого левого знака) и приписывает единицу справа. Ясно что оно любую двоичную запись превратит не более чем за

l шагов в (1...1)=n-1, значит, все

S_k равны, значит, нулю.
Случай, когда n не степень двойки, уже имеет простое доказательство в лоб, примером расстановки

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