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.

А кто вы?

Назовем для удобства сумму $a_1+...+a_k=s_k$.

Пример бесконечных хороших:

$n=2p$ для $p=3k+2$ простых нечетных.

Покажем что если $a^3 \equiv b^3 \pmod {2p}$ то $a \equiv b \pmod {2p}$.

Очевидно $a \equiv b \pmod 2$. Если одно из чисел делится на $p$, то оба делятся на $p$. Берем как взаимнопростые к $p$.

Заметим что $a^{(3)k} \equiv b^{(3)k} \pmod p$. По малой теореме Ферма верно что $a^{p-1=(3)k+1} \equiv b^{p-1=(3)k+1} \equiv 1 \pmod p$. Получаем $a \equiv b \pmod p$ и из этого $a \equiv b \pmod {2p}$.

Из предыдущего выводим что для каждого $k$ можно взять уникальный $1 \leq a_k \leq 2p$ так что $a_k \equiv k^3 \pmod {2p}$, убедимся что все $a_k$ удовлетворяют условие различных четностей. Получаем что $s_k \equiv 1^3+...+k^3=\frac{k^{2}(k+1)^2}{4} \pmod {2p}$, из чего $n=2p$ хорошее для $p=3k+2$ нечетного простого.

Пример бесконечных плохих:

$n=4m$ для $m$ - нечетного.

Допустим что существует хорошее $4m$. Найдутся $x^2_k \equiv s_k \pmod {4m}$, что значит что $x^2_k \equiv s_k \pmod 4$. Покажем что такое невозможно.

Заметим что последовательность остатков $x^2_1, ...., x^2_k$ на 4 обретает форму $[0,1,1,0,0,1,1,0,....]$ или $[1,1,0,0,1,1,0,0,.....]$. Это исходит от факта что последовательность четнестей $s_1,....,s_k$ либо чет, нечет, нечет, чет, либо чет, нечет, нечет, чет..... либо нечет, нечет, чет, чет, нечет, нечет, чет, чет.... от условия различной четности. Тогда возможные остатки значения $a_k=s_k-s_{k-1} \equiv 0,1,3 \pmod 4$ ($s_0=0$), значит $k \equiv 2 \pmod 4$ не входят в значения $a_1,...,a_n$. Противоречие, $4m$ не являются хорошим.

В чем смысл повторного поста вышепоказанных решении