Проблема с нулевой суммой
В чисел теории задачи с нулевой суммой — это определенные виды комбинаторных задач о структуре конечной абелевой группы . Конкретно, учитывая конечную абелеву группу 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] ).
См. также
[ редактировать ]Ссылки
[ редактировать ]- ^ Эрдеш, Пол; Гинзбург А.; Зив, А. (1961). «Теорема аддитивной теории чисел». Бык. Рез. Совет Израиля . 10F : 41–43. Збл 0063.00009 .
- ^ Натансон (1996) стр.48
- ^ Райхер, Кристиан (2007), «О гипотезе Кемница относительно точек решетки на плоскости», The Ramanujan Journal , 13 (1–3): 333–337, arXiv : 1603.06161 , doi : 10.1007/s11139-006-0256- у , S2CID 119600313 , Збл 1126.11011 .
- ^ Гринкевич, DJ (2006), «Взвешенная теорема Эрдеша-Гинзбурга-Зива» (PDF) , Combinatorica , 26 (4): 445–453, doi : 10.1007/s00493-006-0025-y , S2CID 33448594 , Zbl 1121.11018 .
- Герольдингер, Альфред (2009). «Аддитивная теория групп и неединственные факторизации». В Герольдингере, Альфред; Ружа, Имре З. (ред.). Комбинаторная теория чисел и аддитивная теория групп . Курсы повышения квалификации по математике CRM в Барселоне. Эльшольц, К.; Фрейман, Г.; Хамидун, Йо; Хегивари, Н.; Каройи, Г.; Натансон, М.; Солимоси, Дж. ; Станческу, Ю. С предисловием Хавьера Силлеруэло, Марка Ноя и Ориола Серры (координаторов DocCourse). Базель: Биркхойзер. стр. 1 –86. ISBN 978-3-7643-8961-1 . Коллекция 1221.20045 .
- Натансон, Мелвин Б. (1996). Аддитивная теория чисел: обратные задачи и геометрия сумм . Тексты для аспирантов по математике . Том. 165. Шпрингер-Верлаг . ISBN 0-387-94655-1 . Збл 0859.11003 .
Внешние ссылки
[ редактировать ]- «Теорема Эрдеша-Гинзбурга-Зива» , Математическая энциклопедия , EMS Press , 2001 [1994]
- PlanetMath Эрдеш, Гинзбург, Теорема Зива
- Сунь, Чжи-Вэй , «Покрывающие системы, ограниченные суммы, задачи с нулевой суммой и их унификация»
Дальнейшее чтение
[ редактировать ]- Задачи с нулевой суммой - Опрос (журнальная статья в открытом доступе)
- Теория Рамсея с нулевой суммой: графики, последовательности и многое другое (домашняя страница семинара)
- Арье Бялостоцкий , « Деревья с нулевой суммой: обзор результатов и открытых проблем » Н. В. Зауэр (ред.) Р. Е. Вудро (ред.) Б. Сэндс (ред.), Конечная и бесконечная комбинаторика в множествах и логике , Nato ASI Ser. , Клювер Акад. Опубл. (1993) стр. 19–29.
- Ю. Каро, « Задачи с нулевой суммой: обзор » Дискретная математика. , 152 (1996), стр. 93–113.
 | Эта комбинаторике статья, посвященная , незавершена . Вы можете помочь Википедии, расширив ее . |