задачка из sci.math.research

[maxal]

Пусть $n$ - целое положительное число такое, что число $p=2n+1$ является простым.
Определим отображение "штрих" из кольца вычетов $\mathbb{Z}_p=\{ 0, 1, \dots, p-1\}$ во множество $\{ 0, 1, \dots, n\}$ формулой $x' = \min\{ x, p-x \}$.

Доказать, что для любого $L\in\{ 2, 3, \dots, p-2 \}$ выполняется равенство

$$\sum_{x=1}^n |x - (Lx)'| = \frac{n(n+1)}{3}.$$

Здесь произведение $Lx$ рассматривается в кольце $\mathbb{Z}_p$, а все остальные операции - в обычной арифметике.

Пример: $n=6$, $p=13$, $L=3$. Тогда
$\sum\limits_{x=1}^6 |x - (3x)'| = |1-3| + |2-6| + |3-4| + |4-1| + |5-2| + |6-5| = 14$.

[Руст]

Возьмём вычеты по модулю $p$ от $-n$ до $n$. Соответственно сложение и умножение вычетов так же приведём к этому интервалу. Тогда вычисление приводится к виду:

$$S(L)=\sum_{x=1,Lx>0}^n (|(L-1)x|+|(L+1)x|), S(L)=S(L^{-1}).$$

Из последнего получается:

$$S(L)=\frac{1}{p-1} \sum_{k=1}^{p-1} \sum_{x=1,L^kx>0}^n (|(L-1)L^kx|+|(L+1)L^kx|).$$

Отсюда получается независимость от $L$ при обратимости чисел $L-1$ и $L+1$. Для $L=2$ долгое непосредственное вычисление показывает, что результат верен. При этом врде для справедливости утверждения не требуется, чтобы $p$ было простым. Достаточно, чтобы он не делился на $3$ (иначе, число $\frac{n(n+1)}{3}$ не целое) и $L-1$ и $L+1$ обратимы по модулю $p$.

[maxal]

Руст писал(а):

Возьмём вычеты по модулю р от -n до n. Соответственно сложение и умножение вычетов так же приведём к этому интервалу. Тогда вычисление приводится к виду:

$$S(L)=\sum_{x=1,Lx>0}^n (|(L-1)x|+|(L+1)x|),$$

Эта формула неверна.
Верна, например, такая:

$$S(L)=\sum_{x=1,\ Lx>0}^n |(L-1)x|+ \sum_{x=1,\ Lx<0}^n |(L+1)x|$$

Руст писал(а):

$$S(L)=S(L^{-1}).$$

И это откуда?

Руст писал(а):

Отсюда получается независимость от $L$ при обратимости чисел $L-1$ и $L+1$. Для $L=2$ долгое непосредственное вычисление показывает, что результат верен. При этом врде для справедливости утверждения не требуется, чтобы $p$ было простым. Достаточно, чтобы он не делился на $3$ (иначе, число $\frac{n(n+1)}{3}$ не целое) и $L-1$ и $L+1$ обратимы по модулю $p$.

Понятно, что как только доказана независимость от $L$, то дальнейшее просто. Для $L=2$ простота $p$ действительно не требуется, но она нужна для того, чтобы $L-1$ и $L+1$ были всегда обратимы.

[Руст]

$$S(L)=\sum_{x=1,\ Lx>0}^n |(L-1)x|+ \sum_{x=1,\ Lx<0}^n |(L+1)x|=\sum_{x=|L^{-1}y|,y=1}^n |x-|Lx|| =\sum_{y=1}^n ||L^{-1}y|-y|=S(L^{-1})$$

Разбивайте, пожалуйста, длинные формулы и цепочки. Знак =, например, вполне удобное место. // нг

[maxal]

Руст писал(а):

$$\sum_{x=|L^{-1}y|,y=1}^n |x-|Lx|| =\sum_{y=1}^n ||L^{-1}y|-y|=S(L^{-1})$$

Все так, только это к формуле с $L-1$ и $L+1$ имеет слабое отношение.

Кстати, могу предложить еще такое доказательство равенства $S(L)=S(L^{-1})$. Рассмотрим операцию $f(x) = |Lx|$, которая разбивает множество $\{1,2,\dots,n\}$ на циклы вида $x\to f(x)\to f(f(x)) \to \dots \to x$ (можно заметить, что $f^{(k)}(x) = |L^k x|$). При этом $S(L)$ есть ни что иное как сумма модулей разностей всех соседних элементов в этих циклах. Каждый элемент $x$ присутствует в двух таких разностях и не сокращается, только если он больше (меньше) обоих своих соседей по циклу $|Lx|$ и $|L^{-1}x|$. Таким образом получаем формулу:

$$S(L) = 2 \left(\sum_{x=1\atop x >|Lx|,\ x >|L^{-1}x|}^n x - \sum_{x=1\atop x <|Lx|,\ x <|L^{-1}x|}^n x\right)$$

.
Как нетрудно видеть, эта формула инвариантна относительно замены $L$ на $L^{-1}$.

Вернемся к доказательству "независимости от $L$".
Рустем, я не уловил твоей идеи, тем более, что была использована неверная формула.

[Руст]

Я не понял, maxal если ты сам знаешь решение, то какой смысл мне писать громоздкое и не интересное решение.

[maxal]

Руст писал(а):

Я не понял, maxal если ты сам знаешь решение, то какой смысл мне писать громоздкое и не интересное решение.

На данный момент я как раз уперся в доказательство "независимости от $L$". В своем первоначальном решении я нашел пробел, который устранить пока не удалось. Поэтому было бы интересно увидеть твое доказательство. К тому же в первом сообщении ты как-то очень лихо это доказал, только вот используя неверную формулу, и я так и не уловил идею твоего доказательства до конца. А теперь ты почему-то называешь это "громоздким и неинтересным решением". Если тебя не затруднит, я бы все-таки хотел увидеть корректное доказательство факта "независимости от $L$".

[Руст]

Равенство "неверное" я не использовал. На самом деле я переводил суммирование по полной системе вычетов, а потом в одном менял знаки для того, чтобы ограничение делать одинаковым.
Я сводил к двойной сумме. При этом, когда $L-1$ и $L+1$ обратимы можно так перегруппировать члены двойной сумммы, чтобы они соответствовали двойной сумме для $L=2$ (в этом громоздкость). Но есть идея сделать это попроще. Укажу как завтра, если будет время.