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

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

Απόδειξη
Το 1961, οι Paul Erdős, Abraham Ginzburg και Abraham Ziv απέδειξαν ότι γενικά για  (ακέραιοι mod n) ισχύει:Erdős-Ginzburg-Ziv (1961), σσ. 41–43.

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

Υπάρχουν και πιο γενικά αποτελέσματα από αυτό το θεώρημα, όπως το θεώρημα του ΌλσονOlson (1968), σσ. 45-52. και οι εικασίες του Kemnitz που αποδείχθηκαν από τον Christian Reiher το 2003,Reiher (2007), σσ. 333–337. επίσης το σταθμισμένο θεώρημα των Erdős-Ginzburg-Ziv που αποδείχθηκε από τον David J. Grynkiewicz το 2005.Grynkiewicz (2006), σσ. 445–453.

Δείτε επίσης
 Θεωρία παιγνίων

Παραπομπές

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







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

 PlanetMath Erdős, Ginzburg, Ziv Theorem 
 Zhi-Wei Sun, "Covering Systems, Restricted Sumsets, Zero-sum Problems and their Unification" 

Πρόβλημα μηδενικού αθροίσματος
Κατηγορία:Μαθηματικά προβλήματα