Πρόβλημα μηδενικού αθροίσματος

Στη θεωρία αριθμών, το πρόβλημα μηδενικού αθροίσματος είναι μια ορισμένη κατηγορία ερωτημάτων Συνδυαστικής. Σε γενικές γραμμές, έστω μια πεπερασμένη Αβελιανή ομάδα G, το πρόβλημα μηδενικού αθροίσματος για έναν ακέραιο n είναι το ακόλουθο: Βρείτε τον μικρότερο ακέραιο k, έτσι ώστε κάθε ακολουθία των στοιχείων του G με μήκος $k$ να περιέχει n όρους που το άθροισμά τους είναι 0.

Απόδειξη

Το 1961, οι Paul Erdős, Abraham Ginzburg και Abraham Ziv απέδειξαν ότι γενικά για $\mathbb {Z} /n\mathbb {Z}$ (ακέραιοι mod n) ισχύει:

$k=2n-1.\$

Αυτό σημαίνει ρητά ότι κάθε πολυσύνολο από 2n - 1 ακέραιους έχει ένα υποσύνολο μεγέθους n του οποίου το άθροισμα των στοιχείων είναι πολλαπλάσιο του n. Αυτό είναι γνωστό ως το θεώρημα των Erdős-Ginzburg-Ziv, που το διερεύνησαν, και μπορεί να συναχθεί από το θεώρημα Cauchy-Davenport.

Υπάρχουν και πιο γενικά αποτελέσματα από αυτό το θεώρημα, όπως το θεώρημα του Όλσον και οι εικασίες του Kemnitz που αποδείχθηκαν από τον Christian Reiher το 2003, επίσης το σταθμισμένο θεώρημα των Erdős-Ginzburg-Ziv που αποδείχθηκε από τον David J. Grynkiewicz το 2005.

Δείτε επίσης

• Θεωρία παιγνίων

Βιβλιογραφία

• Erdős, Paul; Ginzburg, Abraham; Ziv, Abraham (1961). «A theorem in additive number theory». Bull. Res. Council Israel 10F: 41–43. Zbl 0063.00009. 
• Geroldinger, Alfred (2009). «Additive group theory and non-unique factorizations». Στο: Geroldinger, Alfred· Ruzsa, Imre Z. Combinatorial number theory and additive group theory. Advanced Courses in Mathematics CRM Barcelona. Elsholtz, C.; Freiman, G.; Hamidoune, Y. O.; Hegyvári, N.; Károlyi, G.; Nathanson, M.; Solymosi, J.; Stanchescu, Y. With a foreword by Javier Cilleruelo, Marc Noy and Oriol Serra (Coordinators of the DocCourse). Basel: Birkhäuser. σελίδες 1-86. ISBN 978-3-7643-8961-1. Zbl 1221.20045. 
• Grynkiewicz, David J. (2006), «A Weighted Erdős-Ginzburg-Ziv Theorem», Combinatorica 26 (4): 445–453, doi:10.1007/s00493-006-0025-y, Zbl 1121.11018 
• Nathanson, Melvyn B. (1996). Additive Number Theory: Inverse Problems and the Geometry of Sumsets. Graduate Texts in Mathematics. 165. Springer-Verlag. ISBN 0-387-94655-1. Zbl 0859.11003. 
• Olson, J. E. (1968). «An addition theorem modulo p». J. Combin. Theory. Journal of Combinatorial Theory: 45-52. 
• Reiher, Christian (2007), «On Kemnitz' conjecture concerning lattice-points in the plane», The Ramanujan Journal 13 (1–3): 333–337, doi:10.1007/s11139-006-0256-y, Zbl 1126.11011 

Εξωτερικοί σύνδεσμοι

• Hazewinkel, Michiel, επιμ.. (2001), «Erdős-Ginzburg-Ziv theorem», Encyclopedia of Mathematics, Springer, ISBN 978-1-55608-010-4, http://www.encyclopediaofmath.org/index.php?title=p/e110100 
• PlanetMath Erdős, Ginzburg, Ziv Theorem Αρχειοθετήθηκε 2012-08-05 στο Wayback Machine.
• Zhi-Wei Sun, "Covering Systems, Restricted Sumsets, Zero-sum Problems and their Unification" Αρχειοθετήθηκε 2013-02-03 στο Wayback Machine.