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

Από τη Βικιπαίδεια, την ελεύθερη εγκυκλοπαίδεια
Μετάβαση σε: πλοήγηση, αναζήτηση
Πρόβλημα μηδενικού αθροίσματος
Ταξινόμηση
Dewey 518.47
MSC2010 05-XX

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

Απόδειξη[Επεξεργασία | επεξεργασία κώδικα]

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

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]

Περαιτέρω ανάγνωση[Επεξεργασία | επεξεργασία κώδικα]

Παραπομπές[Επεξεργασία | επεξεργασία κώδικα]

  1. Erdős-Ginzburg-Ziv (1961), σσ. 41–43.
  2. Nathanson (1996), σελ. 48.
  3. Olson (1968), σσ. 45-52.
  4. Reiher (2007), σσ. 333–337.
  5. 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 

Εξωτερικοί σύνδεσμοι[Επεξεργασία | επεξεργασία κώδικα]