Anatoly Vorobey (avva) wrote,
Anatoly Vorobey
avva

Category:

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

Среди любых трех целых чисел найдутся два, сумма которых делится на 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 подмножеств исходных чисел A1...A2m-1, каждое из которых размером p, сумма каждого делится на p, и все они не пересекаются друг с другом.

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

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

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

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

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

a1x1p-1 + a2x2p-1 + ... + a2p-1x2p-1p-1 = 0

x1p-1 + x2p-1 + ... + x2p-1p-1 = 0

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

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


(via, of all places, Computational Complexity blog)
Subscribe
  • Post a new comment

    Error

    default userpic

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 16 comments