Πρόβλημα μηδενικού αθροίσματος
αγγλικά :
γαλλικά :
γερμανικά :
Στη Θεωρία των Αριθμών, το πρόβλημα μηδενικού αθροίσματος (αγγλικά: Zero-sum problem) είναι μια ορισμένη κατηγορία ερωτημάτων Συνδυαστικής. Σε γενικές γραμμές, έστω μια πεπερασμένη Αβελιανή ομάδα G, το πρόβλημα μηδενικού αθροίσματος για έναν ακέραιο n είναι το ακόλουθο: Βρείτε τον μικρότερο ακέραιο k, έτσι ώστε κάθε ακολουθία των στοιχείων του G με μήκος k να περιέχει n όρους που το άθροισμά τους είναι 0.
Απόδειξη
Το 1961, οι Paul Erdős, Abraham Ginzburg και Abraham Ziv απέδειξαν ότι γενικά για \( {\displaystyle \mathbb {Z} /n\mathbb {Z} } \) (ακέραιοι mod n) ισχύει:[1]
\( {\displaystyle k=2n-1.\ } \)
Αυτό σημαίνει ρητά ότι κάθε πολυσύνολο από 2n - 1 ακέραιους έχει ένα υποσύνολο μεγέθους n του οποίου το άθροισμα των στοιχείων είναι πολλαπλάσιο του n. Αυτό είναι γνωστό ως το θεώρημα των Erdős-Ginzburg-Ziv, που το διερεύνησαν, και μπορεί να συναχθεί από το θεώρημα Cauchy-Davenport.[2]
Υπάρχουν και πιο γενικά αποτελέσματα από αυτό το θεώρημα, όπως το θεώρημα του Όλσον[3] και οι εικασίες του Kemnitz που αποδείχθηκαν από τον Christian Reiher το 2003,[4] επίσης το σταθμισμένο θεώρημα των Erdős-Ginzburg-Ziv που αποδείχθηκε από τον David J. Grynkiewicz το 2005.[5]
Περαιτέρω ανάγνωση
Θεωρία παιγνίων
Παραπομπές
Erdős-Ginzburg-Ziv (1961), σσ. 41–43.
Nathanson (1996), σελ. 48.
Olson (1968), σσ. 45-52.
Reiher (2007), σσ. 333–337.
Grynkiewicz (2006), σσ. 445–453.
Βιβλιογραφία
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
PlanetMath Erdős, Ginzburg, Ziv Theorem
Zhi-Wei Sun, "Covering Systems, Restricted Sumsets, Zero-sum Problems and their Unification"
Hellenica World - Scientific Library
Από τη ελληνική Βικιπαίδεια http://el.wikipedia.org . Όλα τα κείμενα είναι διαθέσιμα υπό την GNU Free Documentation License
