Πρόβλημα μηδενικού αθροίσματος
Στη θεωρία αριθμών, το πρόβλημα μηδενικού αθροίσματος είναι μια ορισμένη κατηγορία ερωτημάτων Συνδυαστικής. Σε γενικές γραμμές, έστω μια πεπερασμένη Αβελιανή ομάδα G, το πρόβλημα μηδενικού αθροίσματος για έναν ακέραιο n είναι το ακόλουθο: Βρείτε τον μικρότερο ακέραιο k, έτσι ώστε κάθε ακολουθία των στοιχείων του G με μήκος να περιέχει n όρους που το άθροισμά τους είναι 0.
Απόδειξη
Το 1961, οι Paul Erdős, Abraham Ginzburg και Abraham Ziv απέδειξαν ότι γενικά για (ακέραιοι mod n) ισχύει:[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.
Βιβλιογραφία
- Πρότυπο:Cite journal
- Πρότυπο:Cite book
- Πρότυπο:Citation
- Πρότυπο:Cite book
- Πρότυπο:Cite journal
- Πρότυπο:Citation