โจทย์โอลิมปิกระดับ ม.3

[Catt]

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

[ToT]

เย้ ! ในที่สุดก็มีโจทย์ ม.3 แต่ยากจังเลย ไม่เข้าใจโจทย์เลยอ่ะคับ

โจทย์มันก็เคลียร์นี่ครับ
ลองอ่านดีๆสิครับ

[Catt]

รู้สึกว่าเวลาที่ขึ้นมันไม่ค่อยตรงกับความจริงเลย

post เมื่อ 10.30

[TOP]

เพิ่งอ่านโจทย์เข้าใจ เหมือนกันคือ

โจทย์มีอยู่ว่า ในคนจำนวน 2n+1 คน เมื่อเลือก n คนใดๆมา จะมีคนหนึ่งที่ไม่ได้อยู่ใน n คนที่เลือกมา โดยที่คนนั้นจะรู้จักทุกคนใน n คนที่เลือกมา

เป็นเงื่อนไขเริ่มต้นนั่นเอง
ยังไงก็ตาม ขอผ่านโจทย์ไปให้น้องๆคิดกันบ้าง เดี๋ยวจะไม่มีอะไรคิดกัน ดังนั้นน้อง ToT รีบๆคิดเข้านะครับ

่ผมว่ารูปเดิมของคุณ Catt นั้นก็ดูเข้ากับคุณ Catt ดีนะครับ สงสัยเหมือนกันทำไมหลายคนชอบใช้รูปพ่อมดดำ มันดูลึกลับดีหรือครับ ? สำหรับเรื่องเวลาที่แสดงเป็นเวลาที่เมืองไทยครับ(บวกจากเวลาของเครื่อง server ที่ตั้งอยู่ที่อเมริกาไป 14 ชั่วโมง) ถ้าเวลาไม่ตรงก็มีอยู่ 2 สาเหตุครับ คือ คุณ Catt ไม่ได้อยู่ที่เมืองไทย (ดูจากเวลาที่ไม่ตรงกัน ของคุณ Catt เร็วกว่า 1 ชั่วโมง ก็คือตอนนี้คุณ Catt อยู่แถวๆ มาเลเซีย สิงค์โปร์ กัมพูชา ... ) หรือไม่ก็เครื่อง server ถูกย้ายไปอยู่ที่ Time Zone ใหม่ (กรณีนี้เราจะรอสักระยะหนึ่งเพื่อให้แน่ใจว่า server ไม่ย้ายตำแหน่งอีกแล้ว จึงจะปรับเวลาให้ถูกต้อง ช่วงนี้ก็ต้องยอมรับกันไปก่อนว่าเวลามันช้าไป 1 ชั่วโมงนะครับ) แต่จากการตรวจสอบของผม เกิดจากกรณีหลังครับ ก็ต้องรอดูกันต่อไป

แย่จัง ทำไมคิดไม่ได้ก็ไม่รู้ ผมลองสมมติว่าไม่มีใครรู้จักทุกคน แล้วก็ใช้หลัก extreme ให้ A เป็นคนที่รู้จักคนมากที่สุด ก็ยังหาอะไรไม่ค่อยเจอ hint ให้บ้างก็ดีนะคับ (ไม่ได้ทำโจทย์แนวนี้มานานแล้ว ตั้งแต่ช่วงเดือนมีนา)

[TOP]

Hint ให้ละกันว่า จะมี n + 1 คน ที่รู้จักกันหมด

ไม่รู้ว่าวิธีของคุณTOPนี่จะเป็นวิธีเดียวกันไหม
ยังไงก็ให้น้องๆคิดกันไปก่อน
อีกสักพักจะมาเฉลยล่ะกัน

[ToT]

ยอมแพ้แล้วคับ ลองเอาไปคิดดูวันนึง ยังไม่เห็นแนวทางเลย ไม่เคยทำโจทย์แนวนี้เลยอ่าคับ ควรเริ่มไงดีอ่ะครับ

[Catt]

ก็ถ้าเราเลือกมา n คนแล้วแล้วมีคนนึงที่รู้จักทุกคนในn คนนี้
เราก็เลือกมาครั้งนึง ก็จะมีคนนึงที่รู้จักทั้งnคน แสดงต้องมีคนที่รู้จักกันสมมติเป็นนาย 1 กับนาย 2
เลือกอีกครั้งโดยให้นาย 1กับ 2 อยู่ในกลุ่มด้วย จะได้ว่ามีคนนึงที่ทั้งนาย 1 และ 2 รู้จัก ให้เป็นนาย 3 (สังเกตว่านาย 1 2 3 รู้จักกันหมด)
แล้วเลือกอีกโดยให้นาย 1 2 3 อยู่ในกลุ่มที่ถูกเลือกด้วย
จะได้ว่ามีคนนึงที่นาย 1 2 3 รู้จักให้เป็นาย 4 (สังเกตว่านาย 1 2 3 4 รู้จักกันหมด)
แล้วก็เลือกอีกโดยให้นาย 1 2 3 4 อยู่ในกลุ่มที่ถูกเลือกด้วย แล้วทำแบบนี้ต่อไปก็จะเกิดนาย 5 6 7 ... n (สังเกตว่านาย 1 2 3 4 ...n รู้จักกันหมด)
แล้วเลือกอีกโดยให้นาย 1 2 3 4 ...n อยู่ในกลุ่มที่ถูกเลือกด้วย
จะได้ว่ามีคนนึงที่นาย 1 2 3 4 ...n รู้จักให้เป็นาย n+1 (สังเกตว่านาย 1 2 3 4 ...n+1 รู้จักกันหมด)
จากนั้นเลือก n คนที่เหลือ จะมีคนนึงใน n+1 คนนั้นที่รู้จักทุกคนใน n คนที่เหลือ(สมมติเป็นนาย x) และจากที่ว่านาย 1 2 3 4 ...n+1 รู้จักกันหมด ก็จะได้ว่าคนนั้น(นาย x)รู้จักจักทุกคน
ปล.ถ้าจะเขียนพิสูจน์ข้อนี้ให้สมบูรณ์กว่านี้ควรเขียนโดยใช้ induction แต่นี่ที่ไม่ทำโดยinductionเพราะแค่อยากให้เห็นconceptเท่านั้น

[TOP]

วิธีเดียวกันเลยครับ แต่ผมจะไม่เลือกมาทีเดียว n คน ผมจะเลือกออกมา 1 คนก่อน สมมติว่าเป็นหมายเลข 1 จากนั้นจึงถามคนที่เหลือ ว่ามีใครรู้จักเขาไหม เนื่องจาก 1 ฃ n ดังนั้นจะต้องมีคนรู้จักหมายเลข 1 ก็เลือกออกมา 1 คน เป็นหมายเลข 2 ก็ถามต่อไปอีกว่า มีใครรู้จักพวกเขาไหม(หมายเลข 1 และหมายเลข 2) เนื่องจาก 2 ฃ n ดังนั้นจะต้องมีคนรู้จักหมายเลข 1 และหมายเลข 2 ก็เลือกออกมา 1 คน เป็นหมายเลข 3 ก็ถามต่อไปอีกว่า ... สุดท้ายเมื่อเราได้หมายเลข 1 ถึง หมายเลข n เนื่องจาก n ฃ n ดังนั้นจะต้องมีคนรู้จักหมายเลข 1 ถึง หมายเลข n ก็เลือกออกมา 1 คน เป็นหมายเลข n + 1 ต่อจากนี้ไปเราไม่สามารถบอกได้แล้วว่า จะมีใครรู้จักพวกเขาทั้งหมดหรือไม่ ( n + 1 > n) แต่เรารู้แล้วว่า หมายเลข 1 ถึง หมายเลข n + 1 รู้จักกันหมด

จากนี้ก็ให้มองกลับกันว่า เราไม่เลือกพวกเขาทั้ง n + 1 คน แต่ให้เลือก n คนที่เหลืออยู่(ซึ่งยังไม่ถูกเลือก)แทน ดังนั้นจะต้องมีคนหนึ่งใน n + 1 คน ที่รู้จักทุกคนใน n คนที่เลือกมา และคนๆนั้นก็จะเป็นผู้ที่รู้จักกับทุกๆคนนั่นเอง

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

ปล. ตอนนี้เราแน่ใจแล้วว่า Time Zone คงไม่เปลี่ยนไปอีกแล้ว จึงแก้ไขเวลาให้ถูกต้องเรียบร้อยแล้วครับ

[Catt]

บังเอิญว่างช่วงบ่ายเลยเข้ามาดูนะค่ะ
ก็คิดว่าน้องๆม.ต้นน่าจะได้เห็นความแตกต่างของประเทศเรากับรัสเซีย แล้วหวังว่าน้องๆจะได้ไปฟิตหาความรู้เพิ่มเติม อย่ายอมแพ้เด็กประเทศเขาล่ะ

เกือบได้แล้วเชียว
คิดเหมือนกับพี่ๆทั้งสองเลย ตรงที่เลือกมาก่อนคนนึง(ให้เป็น 1)แล้วมาใส่ในกลุ่มนึง จะต้องอีกคนที่อยู่นอกกลุ่มที่รู้จักหมอนี่(ให้เป็น 2) เสร็จแล้วก็เอาคุณ 2 กับคุณ 1 ใส่กลุ่มเดียวกัน มันก็เลยต้องมีคุณ 3 คุณ 4 คุณ 5 ไปเรื่อยๆ จนถึงคุณ n + 1 แต่ผมคิดแค่ว่าคุณ 1 รู้จักคน n คนอ่ะ คิดไม่ถึงว่าได้ n+1 คนนี้รู้จักกันหมดด้วย (จริงๆ คือคิดไม่ออกว่าจาก hint ที่ให้ แล้วทำอะไรต่อได้) ก็ถือว่าคิดได้นิดนึงก็แล้วกัน เสียดายจริงๆที่คิดไม่ได้
ป.ล. อยากอ่าน The art and craft of problem solving จังเลย หาได้ที่ไหนคับ ขอความกรุณาด้วย

[TOP]

ทีแรกพี่ก็คิดได้แบบน้อง ว่ามันรู้จักแค่ n คน กำลังหาทางทำให้ทั้ง n+1 คน รู้จักกันหมด(ไม่งั้นพิสูจน์ไม่ได้) โดยกำลังหาขั้นตอนมาคัดคน ที่รู้จักคนอื่นน้อยกว่าออกไปเรื่อยๆ แต่พอมาลองเขียนเป็น แผนผังแสดงความสัมพันธ์ก็พบกับความจริงที่มองไม่เห็นทันที

สำหรับหนังสือ "THE ART AND CRAFT OF PROBLEM SOLVING" หาอ่านได้ตามห้องสมุดของมหาวิทยาลัยหลายแห่ง อย่างที่จุฬาก็มีอยู่ 2 เล่มด้วยกันคือ ที่ห้องสมุดคณะครุศาสตร์ กับห้องสมุดคณิตศาสตร์คณะวิทยาศาสตร์ นอกจากหนังสือเล่มนี้แล้ว ยังมีหนังสือดีๆ แนวแก้ปัญหา และรวมปัญหาอีกหลายเล่ม ไว้วันหลัง(ไม่รับรองเวลา) จะแนะนำไว้ในส่วนของหนังสือแนะนำละกัน (เขียนเป็นเมนูทิ้งเอาไว้นานแล้ว ยังไม่ได้เริ่มทำสักที) ว่ามีเล่มไหนน่าสนใจบ้าง หากใครรอไม่ไหว สนใจหนังสือดีๆลองดูได้จาก หัวข้อเก่าของเราเรื่อง แนะหนังสือเตรียมโอลิมปิก

[Catt]

ขอวิจารณ์หนังสือเล่มนี้ตามความเห็นของตัวเองหน่อยล่ะกันค่ะ
ข้อดี คือ มีข้อแนะนำและหลักการในการแก้ปัญหาที่ดี มีทฤษฎีหลากหลาย(คือมีหลายวิชา) มีโจทย์และ hint ให้บางข้อ โจทย์ไม่ง่ายนัก
ข้อเสีย คือ ไม่มีเรื่องเรขาคณิต ทฤษฤีที่มีไม่ลึกเท่าไหร่ ถ้าไม่ทำโจทย์จะไม่ได้ประโยชน์เท่าที่ควร เพราะโจทย์บางข้อในบางเรื่องเป็นทฤษฎีที่ควรรู้ และบางข้อที่เราอยากได้ hint มันก็ดันไม่มีให้

สรุปให้ จาก