Problém s nulovým součtem - Zero-sum problem - Wikipedia
v teorie čísel, problémy s nulovým součtem jsou určité druhy kombinační problémy se strukturou a konečná abelianská skupina. Konkrétně, vzhledem k omezené abelianské skupině G a pozitivní celé číslo n, jeden žádá o nejmenší hodnotu k tak, že každá posloupnost prvků G velikosti k obsahuje n podmínky, které součet 0.
Klasickým výsledkem v této oblasti je věta z roku 1961 Paul Erdős, Abraham Ginzburg, a Abraham Ziv.[1] Dokázali to pro skupinu celých čísel modulo n,
Výslovně to říká, že každý multiset ze dne 2n - 1 celá čísla má podmnožinu velikosti n součet jehož prvků je násobkem n, ale totéž neplatí pro multisety velikosti 2n - 2. (Dolní mez je skutečně dobře vidět: multiset obsahující n - 1 kopie 0 a n - 1 kopie 1 obsahuje č n-subset sčítání na násobek n.) Tento výsledek je znám jako Erdős – Ginzburg – Zivova věta po jeho objevitelích. Lze jej také odvodit z Cauchy – Davenportova věta.[2]
Obecnější výsledky než tato věta existují, například Olsonova věta, Kemnitzova domněnka (prokázáno Christian Reiher v roce 2003[3]) a vážená věta EGZ (prokázáno David J. Grynkiewicz v roce 2005[4]).
Viz také
Reference
- ^ Erdős, Paul; Ginzburg, A .; Ziv, A. (1961). "Věta v teorii aditivních čísel". Býk. Res. Rada Izrael. 10F: 41–43. Zbl 0063.00009.
- ^ Nathanson (1996), s. 48
- ^ Reiher, Christian (2007), „O Kemnitzově domněnce o mřížových bodech v rovině“, Deník Ramanujan, 13 (1–3): 333–337, arXiv:1603.06161, doi:10.1007 / s11139-006-0256-r, Zbl 1126.11011.
- ^ Grynkiewicz, D. J. (2006), „Vážená věta Erdős-Ginzburg-Ziv“ (PDF), Combinatorica, 26 (4): 445–453, doi:10.1007 / s00493-006-0025-r, Zbl 1121.11018.
- Geroldinger, Alfred (2009). "Teorie aditivní skupiny a nejedinečné faktorizace". V Geroldinger, Alfred; Ruzsa, Imre Z. (eds.). Kombinatorická teorie čísel a aditivní teorie grup. Pokročilé kurzy matematiky CRM Barcelona. Elsholtz, C .; Freiman, G .; Hamidoune, Y. O .; Hegyvári, N .; Károlyi, G .; Nathanson, M .; Solymosi, J.; Stanchescu, Y. S předmluvou Javiera Cilleruela, Marca Noye a Oriola Serry (koordinátoři DocCourse). Basilej: Birkhäuser. str.1 –86. ISBN 978-3-7643-8961-1. Zbl 1221.20045.
- Nathanson, Melvyn B. (1996). Teorie aditivních čísel: Inverzní problémy a geometrie součtů. Postgraduální texty z matematiky. 165. Springer-Verlag. ISBN 0-387-94655-1. Zbl 0859.11003.