#1
|
|||
|
|||
Pigeonhole
ผมงงมากๆครับไปเจอมาข้อนึง
1.) เลือกจำนวนนับใดๆ 17 โดยนำมาสร้างเป็นสับเซตที่มีสมาชิก 9 ตัว จงพิสูจน์ว่า มีอย่างน้อย 1 สับเซตที่ผลบวกของสับเซตนั้นหาร 9 ลงตัว 24 สิงหาคม 2012 09:53 : ข้อความนี้ถูกแก้ไขแล้ว 1 ครั้ง, ครั้งล่าสุดโดยคุณ Pain 7th |
#2
|
|||
|
|||
เค้าคงต้องการให้เราแยกออกเป็นกรณีไป การกำหนดมูลเหตุต้องระวังให้ครบถ้วน และมีแนวโน้มจะสอดคล้องกับสิ่งที่โจทย์ต้องการ
หรือ เขียนโปรแกรมโดยใช้ Random Function ตามโจทย์ ซึ่งก็ต้องวิเคราะห์ให้ผลบวกของเซตเท่ากับจำนวนเท่าของ 9 ด้วยหลักรังนกพิราบ ประเมินปริมาณหน่วยความจำที่ต้องใช้ และ อาจจะมีการลดกรณีที่ไม่ตรงตามหลักรังนกพิราบออกไป เช่น กรณีสมาชิกเหมือนกัน 1 2 3.. ตัว กรณีไหนไม่ตรงก็ตัดออก |
#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$ อะไรเป็นนกอะไรเป็นรังลองเซ็ตเองนะครับ ได้ไม่ได้ยังไงก็โพสต์มา
__________________
"ชั่วโมงหน้าต้องดีกว่าเดิม!" |
#4
|
|||
|
|||
อ้อ ลดกรณีที่ไม่ตรงกับเงื่อนไขของโจทย์น่ะครับ ส่วนข้อสังเกตุก็น่าจะดูเหมือนเป็นตัวแทนชุดข้อมูลอย่างที่สุด
*เห้อ ทุกวันนี้รู้ไม่ใช่อย่างที่ฝัน ที่อยากมีอะไรของตนเอง เสียตรงนี้ |
#5
|
|||
|
|||
ยังไปต่อไม่ได้อ่ะครับ ไม่เข้าใจอ่ะครับ
|
#6
|
||||
|
||||
แก่นของการทำโจทย์หลักการรังนกพิราบต้องมองให้ออกให้ได้ครับว่า อะไรเป็นนกอะไรเป็นรัง
ผมอยากให้ทำให้ถึงที่สุดก่อน จะพยายามไม่เขียนเฉลยเต็มๆให้อ่ะครับ ดู $b_{0},b_{1},...,b_{n}$ และ $M_{0},M_{1},...,M_{n-1}$ วิเคราะห์ต่อให้สุดให้ได้ครับ หลังจากนั้นเลือก $n=17$
__________________
"ชั่วโมงหน้าต้องดีกว่าเดิม!" |
#7
|
|||
|
|||
ผมเขียนเท่าที่ผมได้ก่อนนะครับ
$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 $ มันมีกี่ตัวอ่ะครับ |
#8
|
||||
|
||||
สมมติให้ $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$ ก็จบ สรุปได้ว่ามีตามที่โจทย์ต้องการให้พิสูจน์ครับ
__________________
"ชั่วโมงหน้าต้องดีกว่าเดิม!" |
#9
|
||||
|
||||
j-i เลือกได้ด้วยเหรอครับ
__________________
----/---~Alice~ จงรับรู้ไว้ ชื่อแห่งสีสันหนึ่งเดียวที่แสดงผล ---/---- ~Blue~ นี่คือ สีแห่งความหลังอันกว้างใหญ่ของเว็บบอร์ดนี้ |
#10
|
||||
|
||||
มันอาจจะต้องพิสูจน์เพิ่มอีกว่าเลือกได้แน่ๆจากการที่ $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 เสมอไป
__________________
"ชั่วโมงหน้าต้องดีกว่าเดิม!" |
#11
|
|||
|
|||
|
#12
|
|||
|
|||
ถ้าจะเขียนแบบเต็มๆ คงเหมือนเฉลยโอลิมปิคคณิตศาสตร์สมัยก่อน ผมว่าเหมือนกับการวางนัยทั่วไป และใช้ทูลทางคณิตศาสตร์(วิชาต่างๆ น่ะครับ ประยุกต์ให้เข้ากัน) แต่เด็กโอลิมปิกก็ต้องเรียนต่อมหาลัย แม้มีสิทธ์เข้าเรียนได้เลย แต่ก็จะพบความยุ่งยากโดยเฉพาะกลไลการค้าและผลประโยชน์
ส่วนมากเห็นติดตาม Workshop ต่างๆ ที่ต่างประเทศเอา ผมทำไม่ไหวอย่างเค้าแม้จะจบวิศวกรรมมา ขอออกตัวว่าถ้าเป็นไปได้จะมาเฉลยแบบฉบับโอลิมปิคที่ผมแกะเอง |
หัวข้อคล้ายคลึงกัน | ||||
หัวข้อ | ผู้ตั้งหัวข้อ | ห้อง | คำตอบ | ข้อความล่าสุด |
pigeonhole principle ครับ | extreme111 | คอมบินาทอริก | 6 | 26 มีนาคม 2012 16:52 |
The Pigeonhole Principle | Tony | ปัญหาคณิตศาสตร์ทั่วไป | 9 | 08 เมษายน 2005 22:38 |
|
|