Теорема Эрдеша — Гинзбурга — Зива // Андрей Райгородский / Турнир городов 2022

Мы поговорим об одной из самых красивых задач современной комбинаторики. Ее предложили в далеком 1961 году П. Эрдёш, А. Гинзбург и А. Зив, которым удалось доказать следующее замечательное утверждение. Теорема. Из любого множества A = {a_{1}, ..., a_{2n−1}}, состоящего из целых чисел, можно выбрать n чисел, сумма которых делится на n. Разумеется, числа в множестве A из формулировки теоремы не обязаны быть различными. Более того, нам лишь нужно знать, какой остаток от деления на n дают эти числа. Эта теорема послужила отправной точкой для развития целого направления в комбинаторной математике. Науку, которая выросла из нее, принято относить к «аддитивной комбинаторике», т. е. к разделу комбинаторики, в котором изучаются задачи, связанные с отысканием различных множеств чисел, чьи суммы обладают теми или иными интересными свойствами. Доп. материалы: Андрей Райгородский — директор физтех-школы прикладной математики и информатики, доктор физико-математических наук, автор популярных книг по комбинаторике. Летняя конференция Турнира городов, Дубна, 2-11 августа 2022 г.