Pigeonhole

[Pain 7th]

ผมงงมากๆครับไปเจอมาข้อนึง

1.) เลือกจำนวนนับใดๆ 17 โดยนำมาสร้างเป็นสับเซตที่มีสมาชิก 9 ตัว จงพิสูจน์ว่า มีอย่างน้อย 1 สับเซตที่ผลบวกของสับเซตนั้นหาร 9 ลงตัว

[kongp]

เค้าคงต้องการให้เราแยกออกเป็นกรณีไป การกำหนดมูลเหตุต้องระวังให้ครบถ้วน และมีแนวโน้มจะสอดคล้องกับสิ่งที่โจทย์ต้องการ
หรือ เขียนโปรแกรมโดยใช้ Random Function ตามโจทย์ ซึ่งก็ต้องวิเคราะห์ให้ผลบวกของเซตเท่ากับจำนวนเท่าของ 9 ด้วยหลักรังนกพิราบ ประเมินปริมาณหน่วยความจำที่ต้องใช้ และ อาจจะมีการลดกรณีที่ไม่ตรงตามหลักรังนกพิราบออกไป เช่น กรณีสมาชิกเหมือนกัน 1 2 3.. ตัว กรณีไหนไม่ตรงก็ตัดออก

[Keehlzver]

ข้อความเดิมเขียนโดยคุณ kongp

เค้าคงต้องการให้เราแยกออกเป็นกรณีไป การกำหนดมูลเหตุต้องระวังให้ครบถ้วน และมีแนวโน้มจะสอดคล้องกับสิ่งที่โจทย์ต้องการ
หรือ เขียนโปรแกรมโดยใช้ Random Function ตามโจทย์ ซึ่งก็ต้องวิเคราะห์ให้ผลบวกของเซตเท่ากับจำนวนเท่าของ 9 ด้วยหลักรังนกพิราบ ประเมินปริมาณหน่วยความจำที่ต้องใช้ และ อาจจะมีการลดกรณีที่ไม่ตรงตามหลักรังนกพิราบออกไป เช่น กรณีสมาชิกเหมือนกัน 1 2 3.. ตัว กรณีไหนไม่ตรงก็ตัดออก

ปวดหัวจริงๆ
http://world.kapook.com/pin/503f32d638217a6d5b000005

อย่ากดเลย

ให้ $a_{i}$ เป็นจำนวนเต็มบวก $n$ จำนวนใดๆ
นิยาม $b_{0}=0$ และ $b_{i}=\sum a_{i}$
นิยาม $M_{i}= \left\{\,x \in \mathbb{N}\mid x \equiv i \pmod{n} \right\}$ โดยที่ $0 \leq i \leq n-1$
อะไรเป็นนกอะไรเป็นรังลองเซ็ตเองนะครับ ได้ไม่ได้ยังไงก็โพสต์มา

[kongp]

อ้อ ลดกรณีที่ไม่ตรงกับเงื่อนไขของโจทย์น่ะครับ ส่วนข้อสังเกตุก็น่าจะดูเหมือนเป็นตัวแทนชุดข้อมูลอย่างที่สุด

*เห้อ ทุกวันนี้รู้ไม่ใช่อย่างที่ฝัน ที่อยากมีอะไรของตนเอง เสียตรงนี้

[Pain 7th]

ยังไปต่อไม่ได้อ่ะครับ ไม่เข้าใจอ่ะครับ

[Keehlzver]

แก่นของการทำโจทย์หลักการรังนกพิราบต้องมองให้ออกให้ได้ครับว่า อะไรเป็นนกอะไรเป็นรัง
ผมอยากให้ทำให้ถึงที่สุดก่อน จะพยายามไม่เขียนเฉลยเต็มๆให้อ่ะครับ

ดู $b_{0},b_{1},...,b_{n}$ และ $M_{0},M_{1},...,M_{n-1}$
วิเคราะห์ต่อให้สุดให้ได้ครับ หลังจากนั้นเลือก $n=17$

[Pain 7th]

ผมเขียนเท่าที่ผมได้ก่อนนะครับ

$b_n = a_1 +a_2+...+a_n$

$b_1=a_1$

$b_2=a_1+a_2$
.
.
.
$b_{17}=a_1+a_2+...+a_{16}+a_{17}$

โดยหลักรังนกพิราบ จะได้ว่ามีอย่างน้อย 1 ตัวที่มีเศษเหมือนกันจากการหารด้วย 9 ให้เป็น $b_i,b_j$

$9|b_i-b_j$ แต่ผมไม่รู้ว่า $b_i-b_j $ มันมีกี่ตัวอ่ะครับ

[Keehlzver]

สมมติให้ $i<j$
ก็จะได้ว่า $b_{i}=a_{1}+...+a_{i}$ และ $b_{j}=a_{1}+a_{2}+...+a_{i}+a_{i+1}+...+a_{j}$
$b_{j}-b_{i}=a_{i+1}+a_{i+2}+...+a_{j}$
$n \mid b_{j}-b_{i}$ ก็จะได้ว่า $\left\{\,a_{i+1},...,a_{j}\right\}$ เป็นสับเซตหนึ่งของ $\left\{\,a_{1},...,a_{n}\right\}$ ที่ $n$ หารผลบวกของมันลง

ต่อไปเราก็เลือกให้ $n=17$ และ $j-i=8$ ก็จบ สรุปได้ว่ามีตามที่โจทย์ต้องการให้พิสูจน์ครับ

[Thgx0312555]

j-i เลือกได้ด้วยเหรอครับ

[Keehlzver]

มันอาจจะต้องพิสูจน์เพิ่มอีกว่าเลือกได้แน่ๆจากการที่ $j-i+1 > 9$ หรือ $j-i+1 < 9$ ผมมั่นใจว่าเลือกได้

ถ้าหากว่า $j-i$ เลือกไม่ได้จริงๆ ถือว่าบทพิสูจน์ที่ผมทำมา weak กว่าโจทย์ก็ใช้ไม่ได้ครับ
ก็เชิญท่านอื่นต่อไป

กรณีที่ $j-i+1 < 9$ ให้เราเลือกจำนวนเต็มบวกจาก 17 จำนวนที่เลือกมาอีกครั้ง เลือกมา $m$ จำนวนที่ 9 หารผลบวกของมันลง
ซึ่งทำให้ $j-i+1+m = 9$ บวกเพิ่มไปจนกว่าจะได้ซับเซทขนาด 9

กรณีที่ $j-i+1 > 9$ ให้เราดูจำนวนเต็มบวก $j-i+1$ จำนวนที่มี เลือกมา $m$ จำนวนที่ 9 หารผลบวกของมันลง
ซึ่งทำให้ $j-i+1-m = 9$ ลดออกมาจนกว่าจะได้ซับเซทขนาด 9

เพราะว่าสับเซตที่สอดคล้องกับโจทย์ไม่มีแค่เซ็ทเดียว และไม่ได้มีขนาดเป็น 9 เสมอไป

[kongp]

http://demonstrations.wolfram.com/GolayCode/

[kongp]

ถ้าจะเขียนแบบเต็มๆ คงเหมือนเฉลยโอลิมปิคคณิตศาสตร์สมัยก่อน ผมว่าเหมือนกับการวางนัยทั่วไป และใช้ทูลทางคณิตศาสตร์(วิชาต่างๆ น่ะครับ ประยุกต์ให้เข้ากัน) แต่เด็กโอลิมปิกก็ต้องเรียนต่อมหาลัย แม้มีสิทธ์เข้าเรียนได้เลย แต่ก็จะพบความยุ่งยากโดยเฉพาะกลไลการค้าและผลประโยชน์

ส่วนมากเห็นติดตาม Workshop ต่างๆ ที่ต่างประเทศเอา ผมทำไม่ไหวอย่างเค้าแม้จะจบวิศวกรรมมา ขอออกตัวว่าถ้าเป็นไปได้จะมาเฉลยแบบฉบับโอลิมปิคที่ผมแกะเอง