Проблема с нулевой суммой
В теории чисел задачи с нулевой суммой — это определенные виды комбинаторных задач о структуре конечной абелевой группы . Конкретно, учитывая конечную абелеву группу G и положительное целое число n , нужно найти наименьшее значение k такое, что каждая последовательность элементов G размера k содержит n членов, сумма которых равна 0 .
Классическим результатом в этой области является теорема 1961 года Пола Эрдёша , Абрахама Гинзбурга и Абрахама Зива . [1] Они доказали, что для группы целых чисел по модулю n
Явно это говорит о том, что любой мультимножество из 2 n − 1 целых чисел имеет подмножество размера n , сумма элементов которого кратна n , но это не так для мультимножеств размера 2 n − 2. (Действительно, нижняя легко увидеть: мультимножество, содержащее n - 1 копию 0 и n - 1 копию 1, не содержит n -подмножества, сумма которого кратна n .) Этот результат известен как теорема Эрдёша–Гинзбурга–Зива после ее первооткрывателей . . Это также может быть выведено из теоремы Коши-Дэвенпорта . [2]
Существуют более общие результаты, чем эта теорема, такие как теорема Олсона , гипотеза Кемница (доказанная Кристианом Райхером в 2003 г. [3] ) и взвешенная теорема EGZ (доказанная Дэвидом Дж. Гринкевичем в 2005 г. [4] ).