задача с Петербургской олимпиады.

[fadetoblack]

вот одна задача с Петербургской олимпиады.. я сам её не решил, но к сожалению и авторского решения(оно у меня есть) не понял
Из чисел от 1 до p-1, где p - простое число составляются всевозможные наборы, содержащие по 3 различных числа. Для каждого такого набора находим произведение его чисел и делим на p. Доказать, что среди получившихся остатков единиц будет не меньше, чем двоек.

[Kid Kool]

Рассмотрим 2 различных числа a и b (оба от 1 до p-1). Они могут входить в тройку 1-ого типа (те, что в произведении дают 1 при делени на p) тогда и только тогда, когда $\frac {1} {ab}$ не равно ни a, ни b. В противном случа, т.е. $a^2b$ или $ab^2$ равно 1 по модулю p, будем называть {a,b} плохой парой первого типа. Аналогично, вводится определение плохой пары второго типа. Нужно доказать, что плохих пар 1-ого типа не больше, чем второго.
Упорядочим плохие пары 1-ого типа так, чтобы $a^2b = 1$. Когда для a можно подобрать соответствующее b? Когда a не является кубическим корнем из 1 по модулю p. Аналогично, для a можно подобрать b так, чтоб они образовали плохую пару 2-ого типа тогда и только тогда, когда a не является кубическим корнем из 2 по модулю p. Поэтому достаточно показать, что кубических корней из 2 не больше, чем кубических корней из 1.

Если их не более одного, то все доказано, т.к. кубический корень из 1 всегда есть (он равен 1 ). Если кубических корней из 2 хотябы 2, скажем, x и y, то, во-первых, их не более 3-х (сравнение n-ой степени по модулю p имеет не более n решений), а во-вторых, найдется 3 корня из 1 - 1, $\frac {x} {y}$ и $\left({\frac {x} {y}}\right)^2$.

Т.о., все доказано.

Добавлено спустя 1 час 8 минут 38 секунд:

Придумал еще решение.

Во-первых, можно перейти к фактор группе по подгруппе, порожденной кубическими корнями из 1 (это очевидно).

Во-вторых, если существуют кубические корни из 2 по модулю p, например,

$$\alpha$$

, то существует биекция, сопоставляющая тройке 2-ого типа тройку 1-ого, а именно -

$$(x,y,z) -> \left(\frac {x} {\alpha},\frac {y} {\alpha},\frac {z} {\alpha}\right)$$

. А если корней из 2 нету, то существует инъекция:

$$(x,y,z) -> \left(\frac {x} {y},\frac {y} {z},\frac {z} {x}\right)$$

. Инъективность этого отображения (в фактор-группе) предлагается проверить любознательному читателю : ))

[Профессор Снэйп]

В теории чисел совсем не силён, ну вроде что-то получилось. С одной стороны длинно, а с другой стороны:

1) Показано, что двойка тут не при чём и вместо неё можно взять любое положительное число, меньшее $p$.

2) Найден критерий того, когда неравенство превращается в равенство.

3) Доказано, что в случае неравенства произведений с единичным остатком ровно на 3 больше, чем произведений с остатком, равным другому (заранее данному) фиксированному числу.

Так что решил всё-таки написать своё решение. В общем, поехали!

Надо доказать, что количество троек $\langle a,b,c \rangle$, составленных из различных ненулевых элементов $\mathbb{Z}_p$, для которых $abc = 1$ не меньше, чем количество аналогичных троек, также составленных из различных ненулевых элементов $\mathbb{Z}_p$, для которых $abc = t$ (умножение, естественно, рассматривается внутри $\mathbb{Z}_p$, ненулевое $t \in \mathbb{Z}_p$ фиксировано, в исходной постановке задачи $t=2$).

Пусть $u$ --- порождающая мультипликативной группы поля $\mathbb{Z}_p$. Пусть

$$ X = \{ \langle a,b,c \rangle \in [0,p-2]^3 : a \neq b \mathbin{\&} b \neq c \mathbin{\&} a \neq c \} $$

Ещё одна переформулировка задачи выглядит так: доказать, что

$$ | \{ \langle a,b,c \rangle \in X : u^{a+b+c} = 1 \} \geqslant | \{ \langle a,b,c \rangle \in X : u^{a+b+c} = t \} $$

Пусть $v < p-1$ таково, что $u^v = t$. Тогда $u^{a+b+c} = 1 \Leftrightarrow a+b+c$ делится на $p-1$ и $u^{a+b+c} = t \Leftrightarrow a+b+c$ сравнимо с $v$ по модулю $p-1$. Воспринимая компоненты троек, принадлежащих $X$, как элементы $\mathbb{Z}_{p-1}$, получаем ещё одну эквивалентную формулировку исходной задачи: доказать, что $|Y| \geqslant |Z|$, где

$$ Y = \{ \langle a,b,c \rangle \in \mathbb{Z}^3_{p-1} : a+b+c = 0,\, a \neq b,\, b \neq c,\, a \neq c \} $$

и

$$ Z = \{ \langle a,b,c \rangle \in \mathbb{Z}^3_{p-1} : a+b+c = v,\, a \neq b,\, b \neq c,\, a \neq c \} $$

Пусть

$$ Y_1 = \{ \langle a,b,c \rangle \in Y : a = b + 2v \} $$

и

$$ Y_2 = \{ \langle a,b,c \rangle \in Y : a = c + 2v \} $$

Ясно, что $Y_1 \cap Y_2 = \emptyset$. Пусть $Y_3 = Y \setminus (Y_1 \cup Y_2)$. Определим отображение $f$, сопоставляющее каждой тройке $\langle a,b,c \rangle \in Y_3$ тройку $\langle a-v, b+v, c+v \rangle$. Из определений видно, что $f$ инъективно отображает $Y_3$ в $Z$, так что $f(Y_3) \subseteq Z$ и $|Y_3| = |f(Y_3)|$.

Легко видеть, что если $2v=0$, то $Y_3 = Y$ и $f(Y_3)=Z$, так что в будущем будем считать, что $2v \neq 0$. Посчитаем количество элементов в $Y_1$. При задании тройки $\langle a,b,c \rangle$ из $Y_1$ элемент $b$ можно выбрать произвольно, $a$ задаётся однозначно по $b$, а $c$ определяется равенством $a+b+c = 0$. Кроме того, $c$ должен отличаться от $a$ и $b$, так что при выборе $b$ должны учитываться неравенства $3b+2v \neq 0$ и $3b + 4v \neq 0$. Таким образом, $|Y_1|$ равно количеству элементов $b$ в $\mathbb{Z}_{p-1}$, для которых $3b+2v \neq 0$ и $3b + 4v \neq 0$. Ясно, что $|Y_2|$ равно тому же самому.

Посмотрим, какие элементы $Z$ не попадают в образ $f$. Прямо из определений следует, что $\langle a,b,c \rangle \in f(Y_3) \Leftrightarrow \langle a+v,b-v,c-v \rangle \in Y_3$. В случае $\langle a,b,c \rangle \in Z$ отсюда видим, что эта тройка не лежит в образе $f$ тогда и только тогда, когда либо $b = a + 2v$, либо $c = a + 2v$. В силу $b \neq c$ оба равенства не могут выполняться сразу. Если мы хотим выполнить первое равенство, то $a$ можно выбрать произвольно, $b$ однозначно определится по $a$, а $c$ найдётся из равенства $a+b+c=v$. Но $c$ должно отличаться от $a$ и $b$, так что должны выполняться неравенства $3a + v \neq 0$ и $3a + 3v \neq 0$. Таким образом, первое равенство можно выбрать столькими способами, сколько существует элементов $a$ в $\mathbb{Z}_{p-1}$, для которых $3a+v \neq 0$ и $3a + 3v \neq 0$. Количество способов, которыми можно удовлетворить второе неравенство, точно такое же. И поскольку в задаче требуется доказать, что количество способов, которыми можно удовлетворить одно из неравенств, не превышает количества элементов в $Y_1 \cup Y_2$, то у нас появляется ещё одна переформулировка задачи: доказать, что

$$ | \{ x \in \mathbb{Z}_{p-1} : 3x + 2v = 0\, \vee\, 3x + 4v = 0 \}| \leqslant | \{ x \in \mathbb{Z}_{p-1} : 3x + v = 0\, \vee\, 3x + 3v = 0 \}| $$

Можно даже сделать более сильное утверждение: $Y$ отличается от $Z$ на количество элементов, равное разности правой и левой частей этого неравенства.

Ну а тут уже всё совсем легко. Если у какого-то из уравнений $3x+2v=0$, $3x+4v=0$, $3x+v=0$ и $3x+3v=0$ есть корни, то их количество равно $3$ в случае, когда $p-1$ делится на $3$, и $1$ в противном случае. Уравнение $3x+v=0$ имеет корень тогда и только тогда, когда имеет корень уравнение $3x+2v=0$. Действительно, если $x$ корень первого уравнения, то $2x$ --- корень второго, а если $x$ --- корень второго, то $-v-x$~--- корень первого. Аналогично наличие корней у уравнения $3x+4v=0$ равносильно наличию корней у уравнения $3x+2y=0$. Ну а у уравнения $3x+3v=0$ корни есть всегда и мы доказали всё, что надо.

Под конец ещё заметим, что если $p-1$ не делится на $3$, то корни у любого линейного уравнения с коэффициентом $3$ при переменной есть всегда. Сюда же можно приплюсовать случай $2v=0$, исключённый из рассмотрения ранее, поскольку в этом случае уравнение $3x+2v=0$ имеет корень $x=0$.

---------------

Суммируя всё вышесказанное и возвращаясь к исходным обозначениям, получаем, что

1) Если $t$ является кубическим вычетом по модулю $p$, то в исходной задаче неравенство превращается в равенство

2) Если $t$ не является кубическим вычетом по модулю $p$, то количество троек с остатком от произведения равным $1$ на $3$ больше, чем количество троек с остатком от произведения, равным $t$.

Наверное, как-то всё можно было покороче...