avva | о числах и вычетах (математическое)

Среди любых трех целых чисел найдутся два, сумма которых делится на 2 (четна). Это тривиально.

Среди любых пяти целых чисел найдутся три, сумма которых делится на 3. Это просто доказать - даже в уме - перебором остатков.

Верно ли, что среди любых 2n-1 целых чисел найдутся n, сумма которых делится на n? Это верно, и впервые доказано в статье Эрдеша, Гинзбурга и Зива в 1961-м году.

В этой статье Ноги Алона и Моше Дубинера (англ.) приводится пять разных простых доказательств этой теоремы. "Простых" здесь означает примерно на уровне второго курса университета, а не школьной математики. Рекомендую - красивые (и все краткие) доказательства.

Я перескажу здесь под катом одно из них.

Сначала надо доказать, что достаточно показать результат для простых n, из чего он следует для всех остальных. Это довольно просто и доказывается индукцией по числу множителей в разбиении n на простые множители. Пусть n = p*m, где p простое; тогда мы можем предположить, что для p и для m (по индуктивному предположению) результат уже доказан. Пусть у нас есть 2pm-1 чисел; будем произвольным образом брать 2p-1 из них, находить среди этих p таких, что их сумма делится на p, откладывать в сторону, и повторять заново. После 2m-2 таких отборов у нас будет отложено (2m-2)p чисел, и останется 2pm-1-(2m-2)p = 2p-1, поэтому мы сможем проделать это еще один последний раз, и всего мы получим 2m-1 подмножеств исходных чисел A₁...A_2m-1, каждое из которых размером p, сумма каждого делится на p, и все они не пересекаются друг с другом.

Если a_i - сумма всех чисел в A_i, поделенная на p, то из целых чисел a₁...a_2m-1 можно выбрать m таких, сумма которых делится на m. Тогда сумма тех множеств А, что соответствуют выбранным числам a, делится на pm, что и требовалось доказать.

Теперь - доказательство того, что нужный результат верен для любого простого p.

Теорема Шевалье-Уорнинга утверждает следующее о корнях многочленов в конечных полях. Пусть у нас есть конечное поле F харатеристики p, и какое-то количество многочленов от m переменных P_i(x₁, ..., x_m). Если сумма степеней всех многочленов P_i меньше числа переменных m, то количество общих корней всех P_i в F^m делится на характеристику p.

В статье приводится простое, и тоже красивое, доказательство этой теоремы (см. Theorem 2.3).

С помощью этой теоремы можно легко доказать нужное нам утверждение для простых p. Пусть у нас есть 2p-1 целых чисел; рассмотрим систему из двух многочленов над конечным полем Z_p:

a₁x₁^p-1 + a₂x₂^p-1 + ... + a_2p-1x_2p-1^p-1 = 0

x₁^p-1 + x₂^p-1 + ... + x_2p-1^p-1 = 0

У этой системы есть один тривиальный корень (0, 0, ..., 0). Но эта система отвечает условию теоремы Шевалье-Уорнинга: сумма степеней двух многочленов 2(p-1) меньше числа переменных 2p-1. Поэтому согласно теореме число решений делится на p и не может быть единицей. Раз есть одно решение (тривиальное), значит должно быть как минимум еще одно, нетривиальное. Что можно сказать об этом нетривиальном решении?

В поле Z_p любой ненулевой элемент в степени p-1 равен 1 (Малая теорема Ферма). Поэтому в решении второго многочлена каждый ненулевой икс прибавляет к сумме единичку, и значит число ненулевых иксов делится на p, и следовательно равно p (всего переменных 2p-1, так что 2p или больше быть не может, а 0 не может, потому что мы предполагаем нетривиальное решение). В первом многочлене каждый такой ненулевой икс в степени p-1 становится единицей, а все остальные нулями, и поэтому остается ровно p чисел среди a₁...a_2p-1, сумма которых равна 0 по модулю p. Что и требовалось доказать.

(via, of all places, Computational Complexity blog)