42-я Балканская математическая олимпиада. Сараево, Босния и Герцеговины, 2025 год

Целое число $n > 1$ называется хорошим, если существует перестановка $a_1$, $a_2$, $a_3$, $\ldots$, $a_n$ чисел 1, 2, 3, $\ldots$, $n$, такая, что:
   $a_i$ и $a_{i+1}$ имеют различную четность для любого $1\le i\le n-1$;
   cумма $a_1+a_2+\ldots+a_k$ является квадратичным вычетом по модулю $n$ для каждого $1\le k\le n$. Докажите, что существует бесконечно много хороших чисел, а также бесконечно много чисел, которые не являются хорошими.
   Замечание: Целое число $x$ является квадратичным вычетом по модулю $n$, если существует целое число $y$ такое, что $x\equiv y^2 \pmod n$.

Комментарий/решение

Пример для не хороших чисел:

$n=4^x$

Тогда давайте посчитаем сумму всех чисел.

$1+2+...+4^x=4^x(4^x+1)/2=2^{2x-1}$$mod$ $4^x$

Давайте просто убедимся что $2^{2x-1}$ - невычет по $mod$ $4^x$

$2^{2x-1}=y^2$ $mod$ $4^x$

С одной стороны $y^2$ обязано делится на $2^{2x-1}$ Но тогда оно делится и на $2^{2x}$, что уже даёт противоречие

Пример для хороших чисел

$n=p=4k+3$

Выпишем все вычеты по $mod$ $p$. У нас получится некий набор из $\frac{p-1}{2}$ чисел. Давайте все нечетные числа запишем в группу А, все чётные в группу Б. Тогда выстроим нашу последовательность следующим образом:

Сначало будет идти некий элемент А $= x$, а далее $p-x$. Понятно по теореме Жерара что $p-x$ не вычет поэтому мы так можем проделать со всеми элементами А. Далее после последнего $p-x$, будет идти $p$, а затем аналогично с элементами Б. И легко можно убедиться что последовательность подходит, просто у нас сумма всех чисел либо $0$, либо какой то вычет

Красивый пример для хороших чисел:

Возьмем $n=2p$, где $p\equiv 2 \pmod{3}$. Тогда последовательность $a_i \equiv i^3 \pmod{n}$, подходит. $(a_i \leq n)$

Доказательство:

Понятно любые два подряд идущих элемента последовательности имеют разную четность. Теперь докажем что все они разные. Используем следующую лемму:

Если $i^2+ij+j^2$ делится на $p \equiv 2 \pmod{3}$, где $i, j$ целые и $p \in \mathbb{P}$, то $p \mid i, j$. $(*)$

От обратного, пусть

$i^3 \equiv j^3 \pmod{n}$, для каких то $i>j \in \mathbb{Z}$, тогда либо $i-j \equiv 0 \pmod{p}$, или $i-j=p$, откуда $i$ и $j$ имеют разную четность. Но тогда $2 \nmid i^2+ij+j^2$. Если $p \mid i^2+ij+j^2$, то по $(*)$ получим противоречие.

И понятно $a_1+a_2+…+a_k \equiv (1+2+…+k)^2 \pmod{n}$.

Откуда легко следует требуемое.

P.S. Я извиняюсь за то что так плохо выступил на BMO.

А кто вы?