Zero-sum problem (original) (raw)
Στη Θεωρία των Αριθμών, το πρόβλημα μηδενικού αθροίσματος (αγγλικά: Zero-sum problem) είναι μια ορισμένη κατηγορία ερωτημάτων Συνδυαστικής. Σε γενικές γραμμές, έστω μια πεπερασμένη Αβελιανή ομάδα G, το πρόβλημα μηδενικού αθροίσματος για έναν ακέραιο n είναι το ακόλουθο: Βρείτε τον μικρότερο ακέραιο k, έτσι ώστε κάθε ακολουθία των στοιχείων του G με μήκος να περιέχει n όρους που το άθροισμά τους είναι 0.
| Property | Value |
|---|---|
| dbo:abstract | Στη Θεωρία των Αριθμών, το πρόβλημα μηδενικού αθροίσματος (αγγλικά: Zero-sum problem) είναι μια ορισμένη κατηγορία ερωτημάτων Συνδυαστικής. Σε γενικές γραμμές, έστω μια πεπερασμένη Αβελιανή ομάδα G, το πρόβλημα μηδενικού αθροίσματος για έναν ακέραιο n είναι το ακόλουθο: Βρείτε τον μικρότερο ακέραιο k, έτσι ώστε κάθε ακολουθία των στοιχείων του G με μήκος να περιέχει n όρους που το άθροισμά τους είναι 0. (el) En nombroteorio, nulo-suma problemo estas la problemo trovi la plej malgrandan entjeron k tian ke ĉiu vico de eroj de G kun longo k enhavas n erojn kies sumo estas la neŭtra elemento (0), kie G estas kaj n estas donita entjero. En 1961 Paŭlo Erdős, A. Ginzburg kaj A. Ziv pruvis la ĝeneralan rezulton por (la entjeroj mod n): k = 2n-1. En ĉi tiu okazo, la n egalas al amplekso de G, kvankam ĝenerale ĉi tio ne nepras. Eksplicite ĉi tio signifas ke ĉiu multaro de 2n-1 entjeroj havas subaron de amplekso n, la sumo de kies eroj estas oblo de n (kaj do estas 0 module n). Ĉi tiu rezulto estas ĝenerale sciata kiel la EGZ teoremo laŭ ĝiaj esploristo. Pli ĝeneralaj rezultoj ol ĉi tiu teoremo ekzistas - , (pruvita de Christian Reiher en 2003), kaj la (pruvita per D. J. Grynkiewicz en 2005). (eo) En théorie des nombres, les problèmes de la somme nulle forment une classe de questions combinatoires. Dans un groupe abélien fini G, le problème de la somme nulle est de déterminer, pour tout entier n > 0, le plus petit entier k tel que toute suite de k éléments de G contienne une sous-suite de n termes de somme 0. En 1961, Paul Erdős, Abraham Ginzburg et Abraham Ziv ont démontré que pour G égal au groupe additif de l'anneau ℤ/nℤ, ce plus petit k vaut 2n – 1. Ce résultat, appelé le théorème d'Erdős-Ginzburg-Ziv ou « théorème EGZ », peut se déduire du théorème de Cauchy-Davenport. Il possède des généralisations comme le théorème d'Olson, la conjecture de Kemnitz (démontrée par Christian Reiher en 2003) et le « théorème EGZ pondéré » (démontré par David J. Grynkiewicz en 2005). (fr) In number theory, zero-sum problems are certain kinds of combinatorial problems about the structure of a finite abelian group. Concretely, given a finite abelian group G and a positive integer n, one asks for the smallest value of k such that every sequence of elements of G of size k contains n terms that sum to 0. The classic result in this area is the 1961 theorem of Paul Erdős, Abraham Ginzburg, and Abraham Ziv. They proved that for the group of integers modulo n, Explicitly this says that any multiset of 2n − 1 integers has a subset of size n the sum of whose elements is a multiple of n, but that the same is not true of multisets of size 2n − 2. (Indeed, the lower bound is easy to see: the multiset containing n − 1 copies of 0 and n − 1 copies of 1 contains no n-subset summing to a multiple of n.) This result is known as the Erdős–Ginzburg–Ziv theorem after its discoverers. It may also be deduced from the Cauchy–Davenport theorem. More general results than this theorem exist, such as , Kemnitz's conjecture (proved by Christian Reiher in 2003), and the (proved by in 2005). (en) |
| dbo:wikiPageExternalLink | https://archive.org/details/combinatorialnum00gero_834 https://archive.org/details/combinatorialnum00gero_834/page/n13 https://web.archive.org/web/20120805174718/http:/planetmath.org/encyclopedia/ErdHosGinzburgZivTheorem.html http://math.nju.edu.cn/~zwsun/csz.htm |
| dbo:wikiPageID | 2546047 (xsd:integer) |
| dbo:wikiPageLength | 3915 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1087260221 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Davenport_constant dbc:Mathematical_problems dbr:Paul_Erdős dbr:Christian_Reiher dbr:Modular_arithmetic dbr:Multiset dbr:Identity_element dbr:Cauchy–Davenport_theorem dbr:Abraham_Ginzburg dbr:Abraham_Ziv dbc:Combinatorics dbr:Number_theory dbr:Graduate_Texts_in_Mathematics dbr:Kemnitz's_conjecture dbr:József_Solymosi dbc:Paul_Erdős dbr:Integer dbr:Subset_sum_problem dbr:Combinatorial dbr:Springer-Verlag dbr:Finite_abelian_group dbr:Zhi-Wei_Sun dbr:David_J._Grynkiewicz dbr:Olson's_theorem dbr:Weighted_EGZ_theorem |
| dbp:id | p/e110100 (en) |
| dbp:title | Erdős-Ginzburg-Ziv theorem (en) |
| dbp:wikiPageUsesTemplate | dbt:Springer dbt:Cite_book dbt:Reflist |
| dct:subject | dbc:Mathematical_problems dbc:Combinatorics dbc:Paul_Erdős |
| rdf:type | yago:WikicatMathematicalProblems yago:Abstraction100002137 yago:Attribute100024264 yago:Condition113920835 yago:Difficulty114408086 yago:Problem114410605 yago:State100024720 |
| rdfs:comment | Στη Θεωρία των Αριθμών, το πρόβλημα μηδενικού αθροίσματος (αγγλικά: Zero-sum problem) είναι μια ορισμένη κατηγορία ερωτημάτων Συνδυαστικής. Σε γενικές γραμμές, έστω μια πεπερασμένη Αβελιανή ομάδα G, το πρόβλημα μηδενικού αθροίσματος για έναν ακέραιο n είναι το ακόλουθο: Βρείτε τον μικρότερο ακέραιο k, έτσι ώστε κάθε ακολουθία των στοιχείων του G με μήκος να περιέχει n όρους που το άθροισμά τους είναι 0. (el) En nombroteorio, nulo-suma problemo estas la problemo trovi la plej malgrandan entjeron k tian ke ĉiu vico de eroj de G kun longo k enhavas n erojn kies sumo estas la neŭtra elemento (0), kie G estas kaj n estas donita entjero. En 1961 Paŭlo Erdős, A. Ginzburg kaj A. Ziv pruvis la ĝeneralan rezulton por (la entjeroj mod n): k = 2n-1. En ĉi tiu okazo, la n egalas al amplekso de G, kvankam ĝenerale ĉi tio ne nepras. Pli ĝeneralaj rezultoj ol ĉi tiu teoremo ekzistas - , (pruvita de Christian Reiher en 2003), kaj la (pruvita per D. J. Grynkiewicz en 2005). (eo) En théorie des nombres, les problèmes de la somme nulle forment une classe de questions combinatoires. Dans un groupe abélien fini G, le problème de la somme nulle est de déterminer, pour tout entier n > 0, le plus petit entier k tel que toute suite de k éléments de G contienne une sous-suite de n termes de somme 0. En 1961, Paul Erdős, Abraham Ginzburg et Abraham Ziv ont démontré que pour G égal au groupe additif de l'anneau ℤ/nℤ, ce plus petit k vaut 2n – 1. Ce résultat, appelé le théorème d'Erdős-Ginzburg-Ziv ou « théorème EGZ », peut se déduire du théorème de Cauchy-Davenport. (fr) In number theory, zero-sum problems are certain kinds of combinatorial problems about the structure of a finite abelian group. Concretely, given a finite abelian group G and a positive integer n, one asks for the smallest value of k such that every sequence of elements of G of size k contains n terms that sum to 0. The classic result in this area is the 1961 theorem of Paul Erdős, Abraham Ginzburg, and Abraham Ziv. They proved that for the group of integers modulo n, (en) |
| rdfs:label | Satz von Erdős-Ginzburg-Ziv (de) Πρόβλημα μηδενικού αθροίσματος (el) Nulo-suma problemo (eo) Problème de la somme nulle (fr) Zero-sum problem (en) |
| owl:sameAs | freebase:Zero-sum problem yago-res:Zero-sum problem wikidata:Zero-sum problem dbpedia-de:Zero-sum problem dbpedia-el:Zero-sum problem dbpedia-eo:Zero-sum problem dbpedia-fr:Zero-sum problem dbpedia-hu:Zero-sum problem https://global.dbpedia.org/id/4tDhd |
| prov:wasDerivedFrom | wikipedia-en:Zero-sum_problem?oldid=1087260221&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:Zero-sum_problem |
| is dbo:knownFor of | dbr:Abraham_Ginzburg |
| is dbo:wikiPageDisambiguates of | dbr:Sum |
| is dbo:wikiPageRedirects of | dbr:Erdoes-Ginzburg-Ziv_theorem dbr:Erdös-Ginzburg-Ziv_theorem dbr:Erdos-Ginzburg-Ziv_theorem dbr:Erdos–Ginzburg–Ziv_theorem dbr:Erdős-Ginzburg-Ziv_theorem dbr:Erdős–Ginzburg–Ziv_theorem dbr:EGZ dbr:EGZ_theorem dbr:Zero-sum_problems |
| is dbo:wikiPageWikiLink of | dbr:Christian_Reiher dbr:Sum dbr:Abraham_Ginzburg dbr:Abraham_Ziv dbr:Barycentric-sum_problem dbr:Erdoes-Ginzburg-Ziv_theorem dbr:Erdös-Ginzburg-Ziv_theorem dbr:Kemnitz's_conjecture dbr:Sun_Zhiwei dbr:Zero_sum_(disambiguation) dbr:List_of_things_named_after_Paul_Erdős dbr:Erdos-Ginzburg-Ziv_theorem dbr:Erdos–Ginzburg–Ziv_theorem dbr:Erdős-Ginzburg-Ziv_theorem dbr:Erdős–Ginzburg–Ziv_theorem dbr:EGZ dbr:EGZ_theorem dbr:Zero-sum_problems |
| is foaf:primaryTopic of | wikipedia-en:Zero-sum_problem |