ปัญหาผลรวมเป็นศูนย์
ในทฤษฎีจำนวนปัญหาผลรวมเป็นศูนย์ เป็นปัญหา เชิงการจัดเรียงบางประเภทเกี่ยวกับโครงสร้างของกลุ่มอาเบเลียนจำกัดกล่าวคือ เมื่อกำหนดกลุ่มอาเบเลียนจำกัดGและจำนวนเต็ม บวก nแล้ว เราจะถามหาค่าk ที่น้อยที่สุด ที่ทำให้ลำดับของสมาชิกทุกตัวในGที่มีขนาดkประกอบด้วยnพจน์ที่รวมกันได้เป็น0
ผลลัพธ์คลาสสิกในพื้นที่นี้คือทฤษฎีบทปี 1961 ของPaul Erdős , Abraham GinzburgและAbraham Ziv [ 1 ] พวก เขาพิสูจน์ว่าสำหรับกลุ่มของจำนวนเต็มมอดูลn ,
โดยชัดเจนแล้ว สิ่งนี้ระบุว่ามัลติเซต ใดๆ ของ จำนวนเต็ม 2n − 1 จะมีซับเซตขนาดnซึ่งผลรวมของสมาชิกในซับเซตนั้นเป็นพหุคูณของnแต่จะไม่เป็นเช่นนั้นสำหรับมัลติเซตขนาด 2n − 2 (อันที่จริง ขอบล่างนั้นเห็นได้ง่าย: มัลติเซตที่มี0 จำนวนn − 1 ชุด และ 1 จำนวน n − 1 ชุด จะไม่มี ซับเซตขนาด nที่ผลรวมเป็นพหุคูณของn ) ผลลัพธ์นี้เรียกว่าทฤษฎีบท Erdős–Ginzburg–Zivตามชื่อผู้ค้นพบ นอกจากนี้ยังสามารถอนุมานได้จากทฤษฎีบทCauchy–Davenport [ 2 ]
มีผลลัพธ์ทั่วไปมากกว่าทฤษฎีบทนี้ เช่นทฤษฎีบทของ Olson ข้อสันนิษฐานของ Kemnitz ( พิสูจน์โดยChristian Reiherในปี 2003 [ 3 ] ) และทฤษฎีบท EGZ แบบถ่วงน้ำหนัก (พิสูจน์โดยDavid J. Grynkiewiczในปี 2005 [ 4 ] )
ดูเพิ่มเติม
ลิงก์ภายนอก
- "ทฤษฎีบท Erdös-Ginzburg-Ziv" , สารานุกรมคณิตศาสตร์ , EMS Press , 2001 [1994]
- PlanetMath Erdős, Ginzburg, ทฤษฎีบท Ziv
- ซุน จื้อเหว่ย , "ระบบการครอบคลุม, เซตผลรวมที่จำกัด, ปัญหาผลรวมเป็นศูนย์ และการรวมเข้าด้วยกัน"
อ่านเพิ่มเติม
- ปัญหาผลรวมเป็นศูนย์ - การสำรวจ (บทความวารสารที่เข้าถึงได้ฟรี)
- ทฤษฎีแรมซีย์ผลรวมเป็นศูนย์: กราฟ ลำดับ และอื่นๆ (หน้าหลักของเวิร์กช็อป)
- Arie Bialostocki , " ต้นไม้ผลรวมเป็นศูนย์: การสำรวจผลลัพธ์และปัญหาที่ยังเปิดอยู่ " NW Sauer (บรรณาธิการ) RE Woodrow (บรรณาธิการ) B. Sands (บรรณาธิการ), การจัดเรียงเชิงจำกัดและอนันต์ในเซตและตรรกะ , ชุด Nato ASI , สำนักพิมพ์ Kluwer Acad. (1993) หน้า 19–29
- Y. Caro, " ปัญหาผลรวมเป็นศูนย์: บทสำรวจ " คณิตศาสตร์เชิงดิสครีต , 152 (1996) หน้า 93–113