о числах и вычетах (математическое)
Dec. 18th, 2009 12:58 am![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
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 подмножеств исходных чисел 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)
Среди любых пяти целых чисел найдутся три, сумма которых делится на 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)
