|
|
|||||||
| สมัครสมาชิก | คู่มือการใช้ | รายชื่อสมาชิก | ปฏิทิน | ข้อความวันนี้ | ค้นหา |
  |
|
|
เครื่องมือของหัวข้อ | ค้นหาในหัวข้อนี้ |
|
#1
03 พฤศจิกายน 2001, 17:43
|
|||
|
|||
โจทย์โอลิมปิกระดับ ม.3
เป็นโจทย์โอลิมปิกของรัสเซียระดับ Form 9 เมื่อเทียบกับประเทศไทย ก็ประมาณ ม.3
สอบเมื่อ 10 เม.ย. 44 นี่เอง โจทย์มีอยู่ว่า ในคนจำนวน 2n+1 คน เมื่อเลือก n คนใดๆมา จะมีคนหนึ่งที่ไม่ได้อยู่ใน n คนที่เลือกมา โดยที่คนนั้นจะรู้จักทุกคนใน n คนที่เลือกมา จงพิสูจน์ว่ามีคนที่รู้จักทุกคน ปล.ถึงเป็นโจทย์ระดับม.3 แต่ใครที่ไม่ใช่ม.3ก็ทำได้นะ และในข้อสอบทั้งชุดคิดว่าข้อนี้ง่ายสุดแล้วล่ะ แต่ถึงอย่างนั้นก็ตาม ก็คิดว่ามันไม่ง่ายมากนัก 
|
|
#3
04 พฤศจิกายน 2001, 08:48
|
|||
|
|||
|
โจทย์มันก็เคลียร์นี่ครับ
ลองอ่านดีๆสิครับ
|
|
#5
04 พฤศจิกายน 2001, 19:17
|
||||
|
||||
เพิ่งอ่านโจทย์เข้าใจ เหมือนกันคือ
อ้างอิง:
ยังไงก็ตาม ขอผ่านโจทย์ไปให้น้องๆคิดกันบ้าง เดี๋ยวจะไม่มีอะไรคิดกัน ดังนั้นน้อง ToT รีบๆคิดเข้านะครับ  ่ผมว่ารูปเดิมของคุณ Catt นั้นก็ดูเข้ากับคุณ Catt ดีนะครับ สงสัยเหมือนกันทำไมหลายคนชอบใช้รูปพ่อมดดำ มันดูลึกลับดีหรือครับ ? สำหรับเรื่องเวลาที่แสดงเป็นเวลาที่เมืองไทยครับ(บวกจากเวลาของเครื่อง server ที่ตั้งอยู่ที่อเมริกาไป 14 ชั่วโมง) ถ้าเวลาไม่ตรงก็มีอยู่ 2 สาเหตุครับ คือ คุณ Catt ไม่ได้อยู่ที่เมืองไทย (ดูจากเวลาที่ไม่ตรงกัน ของคุณ Catt เร็วกว่า 1 ชั่วโมง ก็คือตอนนี้คุณ Catt อยู่แถวๆ มาเลเซีย สิงค์โปร์ กัมพูชา ... ) หรือไม่ก็เครื่อง server ถูกย้ายไปอยู่ที่ Time Zone ใหม่ (กรณีนี้เราจะรอสักระยะหนึ่งเพื่อให้แน่ใจว่า server ไม่ย้ายตำแหน่งอีกแล้ว จึงจะปรับเวลาให้ถูกต้อง ช่วงนี้ก็ต้องยอมรับกันไปก่อนว่าเวลามันช้าไป 1 ชั่วโมงนะครับ) แต่จากการตรวจสอบของผม เกิดจากกรณีหลังครับ ก็ต้องรอดูกันต่อไป
__________________
The difference between school and life? In school, you're taught a lesson and then given a test. In life, you're given a test that teaches you a lesson. 04 พฤศจิกายน 2001 19:30 : ข้อความนี้ถูกแก้ไขแล้ว 3 ครั้ง, ครั้งล่าสุดโดยคุณ TOP
|
|
#6
04 พฤศจิกายน 2001, 20:37
|
|||
|
|||
|
แย่จัง ทำไมคิดไม่ได้ก็ไม่รู้ ผมลองสมมติว่าไม่มีใครรู้จักทุกคน แล้วก็ใช้หลัก extreme ให้ A เป็นคนที่รู้จักคนมากที่สุด ก็ยังหาอะไรไม่ค่อยเจอ hint ให้บ้างก็ดีนะคับ (ไม่ได้ทำโจทย์แนวนี้มานานแล้ว ตั้งแต่ช่วงเดือนมีนา)
|
|
#7
05 พฤศจิกายน 2001, 07:03
|
||||
|
||||
Hint ให้ละกันว่า จะมี n + 1 คน ที่รู้จักกันหมด
__________________
The difference between school and life? In school, you're taught a lesson and then given a test. In life, you're given a test that teaches you a lesson.
|
|
#8
05 พฤศจิกายน 2001, 07:46
|
|||
|
|||
|
ไม่รู้ว่าวิธีของคุณTOPนี่จะเป็นวิธีเดียวกันไหม
ยังไงก็ให้น้องๆคิดกันไปก่อน อีกสักพักจะมาเฉลยล่ะกัน
|
|
#10
08 พฤศจิกายน 2001, 07:24
|
|||
|
|||
|
ก็ถ้าเราเลือกมา 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เท่านั้น
|
|
#11
08 พฤศจิกายน 2001, 11:06
|
||||
|
||||
|
วิธีเดียวกันเลยครับ แต่ผมจะไม่เลือกมาทีเดียว 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 คงไม่เปลี่ยนไปอีกแล้ว จึงแก้ไขเวลาให้ถูกต้องเรียบร้อยแล้วครับ
__________________
The difference between school and life? In school, you're taught a lesson and then given a test. In life, you're given a test that teaches you a lesson. 08 พฤศจิกายน 2001 12:08 : ข้อความนี้ถูกแก้ไขแล้ว 1 ครั้ง, ครั้งล่าสุดโดยคุณ TOP
|
|
#13
08 พฤศจิกายน 2001, 19:03
|
|||
|
|||
|
เกือบได้แล้วเชียว
คิดเหมือนกับพี่ๆทั้งสองเลย ตรงที่เลือกมาก่อนคนนึง(ให้เป็น 1)แล้วมาใส่ในกลุ่มนึง จะต้องอีกคนที่อยู่นอกกลุ่มที่รู้จักหมอนี่(ให้เป็น 2) เสร็จแล้วก็เอาคุณ 2 กับคุณ 1 ใส่กลุ่มเดียวกัน มันก็เลยต้องมีคุณ 3 คุณ 4 คุณ 5 ไปเรื่อยๆ จนถึงคุณ n + 1 แต่ผมคิดแค่ว่าคุณ 1 รู้จักคน n คนอ่ะ คิดไม่ถึงว่าได้ n+1 คนนี้รู้จักกันหมดด้วย (จริงๆ คือคิดไม่ออกว่าจาก hint ที่ให้ แล้วทำอะไรต่อได้) ก็ถือว่าคิดได้นิดนึงก็แล้วกัน เสียดายจริงๆที่คิดไม่ได้ ป.ล. อยากอ่าน The art and craft of problem solving จังเลย หาได้ที่ไหนคับ ขอความกรุณาด้วย
|
|
#14
08 พฤศจิกายน 2001, 19:58
|
||||
|
||||
|
ทีแรกพี่ก็คิดได้แบบน้อง ว่ามันรู้จักแค่ n คน กำลังหาทางทำให้ทั้ง n+1 คน รู้จักกันหมด(ไม่งั้นพิสูจน์ไม่ได้) โดยกำลังหาขั้นตอนมาคัดคน ที่รู้จักคนอื่นน้อยกว่าออกไปเรื่อยๆ แต่พอมาลองเขียนเป็น แผนผังแสดงความสัมพันธ์ก็พบกับความจริงที่มองไม่เห็นทันที
สำหรับหนังสือ "THE ART AND CRAFT OF PROBLEM SOLVING" หาอ่านได้ตามห้องสมุดของมหาวิทยาลัยหลายแห่ง อย่างที่จุฬาก็มีอยู่ 2 เล่มด้วยกันคือ ที่ห้องสมุดคณะครุศาสตร์ กับห้องสมุดคณิตศาสตร์คณะวิทยาศาสตร์ นอกจากหนังสือเล่มนี้แล้ว ยังมีหนังสือดีๆ แนวแก้ปัญหา และรวมปัญหาอีกหลายเล่ม ไว้วันหลัง(ไม่รับรองเวลา) จะแนะนำไว้ในส่วนของหนังสือแนะนำละกัน (เขียนเป็นเมนูทิ้งเอาไว้นานแล้ว ยังไม่ได้เริ่มทำสักที) ว่ามีเล่มไหนน่าสนใจบ้าง หากใครรอไม่ไหว สนใจหนังสือดีๆลองดูได้จาก หัวข้อเก่าของเราเรื่อง แนะหนังสือเตรียมโอลิมปิก 
__________________
The difference between school and life? In school, you're taught a lesson and then given a test. In life, you're given a test that teaches you a lesson. 08 พฤศจิกายน 2001 20:18 : ข้อความนี้ถูกแก้ไขแล้ว 1 ครั้ง, ครั้งล่าสุดโดยคุณ TOP
|
|
#15
09 พฤศจิกายน 2001, 21:38
|
|||
|
|||
|
ขอวิจารณ์หนังสือเล่มนี้ตามความเห็นของตัวเองหน่อยล่ะกันค่ะ
ข้อดี คือ มีข้อแนะนำและหลักการในการแก้ปัญหาที่ดี มีทฤษฎีหลากหลาย(คือมีหลายวิชา) มีโจทย์และ hint ให้บางข้อ โจทย์ไม่ง่ายนัก ข้อเสีย คือ ไม่มีเรื่องเรขาคณิต ทฤษฤีที่มีไม่ลึกเท่าไหร่ ถ้าไม่ทำโจทย์จะไม่ได้ประโยชน์เท่าที่ควร เพราะโจทย์บางข้อในบางเรื่องเป็นทฤษฎีที่ควรรู้ และบางข้อที่เราอยากได้ hint มันก็ดันไม่มีให้ สรุปให้ จาก 09 พฤศจิกายน 2001 21:39 : ข้อความนี้ถูกแก้ไขแล้ว 1 ครั้ง, ครั้งล่าสุดโดยคุณ Catt
|
| |
|
|
