В 1961 году Эрдёшу, Гинзбургу и Зиву удалось доказать красивейшее утверждение.
Из любых (2n-1) целых чисел можно выбрать n, сумма которых делится на n.
Сейчас существует несколько доказательств этой теоремы. Приведём одно из них.
Начнём с леммы, позволяющей доказывать утверждение только для простых чисел.
Лемма 1. Пусть утверждение верно для n=a и n=b. Тогда оно верно и для n=ab.
Доказательство. Чтобы нам было легче думать, переформулируем в терминах среднего арифметического. Т.е. будем добиваться того, чтобы нашлись такие x[1], x[2], ..., x[n], что (x[1]+x[2]+...+x[n])/n было целым числом.
Пусть даны произвольные 2ab-1 чисел. Так как утверждение верно для n=b, найдутся 2b-1 число, из которых можно выбрать b, чтобы их сумма делилась на b. Сделаем такую операцию (2a-1) раз. Получим (2a-1) наборов по b чисел, в каждом из которых среднее арифметическое b чисел - целое.
А раз утверждение равно при n=a, то из этих (2a-1) средних арифметических сможем выбрать a, что сумма делилась на a. Так получим ab чисел, среднее арифметическое которых делится на ab. Лемма доказана.
Лемма 2. Пусть p - простое число. И пусть даны r (0<r<p) целых чисел b[1], b[2], ..., b[r] (0<b[i]<p для всех i). Тогда из этих чисел можно составить хотя r+1 сумм, дающих разные остатки при делении на p (при этом разрешается брать сумму "пустого множества слагаемых", которая предполагается равной нулю).
Доказательство. При r=1 утверждение очевидно: эти остатки - 0 и b[1]. Предположим, что утверждение верно при r=k<p-1 и неверно при r=k+1.
Пусть суммы из k слагаемых дают разные остатки 0, s[1], s[2], ..., s[k]. Тогда после присоединения b=b[k+1] их число не должно увеличиться, т.е. все суммы (по модулю p)
0+b, s[1]+b, s[2]+b, ..., s[k]+b
содержатся во множестве {0,s[1],s[2],..., s[k]}. Но тогда это множество заведомо содержит в себе элементы {0,b,2b,...,(p-1)b}. Но легко показать, что все эти элементы различны. Таким образом, получили противоречие с предположением. Лемма доказана.
Для решения исходной задачи осталось немного.
Пусть a[1]<=a[2]<...<a[2p-1] - остатки при делении наших (2p-1) чисел на p.
Рассмотрим ещё числа a[p+1]-a[2], ..., a[2p-1]-a[p]. Если хотя бы одно из чисел равно нулю, то утверждение, очевидно, доказано (нашли p чисел с одинаковыми остатками). Значит, все эти разности отличны от 0.
Найдём теперь остаток x от деления (a[1]+a[2]+...+a[p]) на p. Если x=0, то задача решена. Пусть это не так. Из леммы 2 следует, что мы можем составить из разностей a[p+1]-a[2], ..., a[2p-1]-a[p] сумму, остаток которой при делении на p, равен p-x.
Добавив эти разности к (a[1]+a[2]+...+a[p]) и приведя подобные, получим p чисел, сумма которых делится на p.
В 1983 году А. Кемниц придумал одно очень естественное обобщение задачи Эрдёша – Гинзбурга – Зива. Он предложил вместо целых чисел рассматривать пары целых чисел, которые представляют собой точки на обычной плоскости, имеющие целые координаты. Рассмотрим произвольное множество точек A={(a[1], b[1]), ..., (a[f] , b[f])}. Сложим любые n точек из множества A покоординатно. Скажем, что полученная сумма (также являющаяся точкой на плоскости) делится на n, если обе ее координаты делятся на n. Иными словами, полученная при сложении точка должна иметь вид (na, nb), где a, b ∈ Z. Вопрос: при каком f мы можем гарантировать наличие в A подмножества мощности n, сумма элементов которого делится на n?
Кемниц высказал гипотезу: f=4n−3. Эта гипотеза оказалась «крепким орешком». Для нескольких маленьких значений n ее «вручную» проверили сам Кемниц и Х. Харборт. Затем Н. Алон и М. Дубинер в 1993 году показали, что f<=6n−5. В 2000 году Л. Роньяи установил неравенство f<=4n−2, и лишь в 2003 году гипотезу «дожал» Х. Райхер.
Дальше можно рассматривать точно не на плоскости, а в d-мерном пространстве. Ответ на эту задачу будем обозначать f(n,d)
Даже в трёхмерном случае задача далека от решения. В 2004 году Х. Элсхольц сумел доказать, что f(n,3)>=9n−8 при всех нечетных n.
Перечислю ещё некоторое количество уже доказанных фактов про многомерную задачу.
f(3, 3) = 19 (Харборт, 1973);
f(3, 4) = 41 (Дж. Пеллегрино, Т. Браун, Й. Булер, Дж. Бреннер, Кемниц, 1983);
f(3, 5) = 91 (И. Эдель, С. Ферре, И. Ландьев, Л. Сторм, 2002);
f (2^a,d) = 2^d (2^a−1)+1 (Харборт, 1973);
225<=f(3, 6)<=229 (Эдель, Ферре, Ландьев, Сторм, 2002);
f(3, 18) > 300 · 2^12 (Р. Грехем, П. Франкл, В. Рёдль, 1987);
f(3, d) > 2.217389^d при достаточно больших d (Эдель, 2004);
f(3, d)<=2·3^d/d (Р. Мешулам, 1995);
f(n, d) > 2.08^d для нечетных n и достаточно больших d (Элсхольц, 2004).
Алон и Дубинер доказали, что f(n, d) <= c(d)n, где c(d) - некоторая функция, зависящая от d, но не зависящая от n. Доказано, что c(d) > 2^d · 1.125^[d/3].
Другое решение исходной задачи, а также решение в двумерном случае можно найти в статье
А. М. Райгородский, “Задача Эрдёша – Гинзбурга – Зива и ее окрестности”, Матем. просв., сер. 3, 16, Изд-во МЦНМО, М., 2012, 132–144 (http://www.mathnet.ru/links/4ab4f47352dc9b0cf004b5db93c41ff8/mp294.pdf)