Πρόβλημα μηδενικού αθροίσματος
Στη Θεωρία των Αριθμών, το πρόβλημα μηδενικού αθροίσματος (αγγλικά: Zero-sum problem) είναι μια ορισμένη κατηγορία ερωτημάτων Συνδυαστικής. Σε γενικές γραμμές, έστω μια πεπερασμένη Αβελιανή ομάδα 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.
Βιβλιογραφία[επεξεργασία]
- Erdős, Paul; Ginzburg, Abraham; Ziv, Abraham (1961). «A theorem in additive number theory». Bull. Res. Council Israel 10F: 41–43. Πρότυπο:Zbl.
- Script error: No such module "citation/CS1".
- Grynkiewicz, David J. (2006), «A Weighted Erdős-Ginzburg-Ziv Theorem», Combinatorica 26 (4): 445–453, doi: , Πρότυπο:Zbl
- Script error: No such module "citation/CS1".
- 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: , Πρότυπο:Zbl
Εξωτερικοί σύνδεσμοι[επεξεργασία]
- Πρότυπο:Springer
- 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.
This article "Πρόβλημα μηδενικού αθροίσματος" is from Wikipedia. The list of its authors can be seen in its historical and/or the page Edithistory:Πρόβλημα μηδενικού αθροίσματος. Articles copied from Draft Namespace on Wikipedia could be seen on the Draft Namespace of Wikipedia and not main one.
This page exists already on Wikipedia. |