creatio ex nihilo

ศล
Location :
กรุงเทพ Thailand

[Profile ทั้งหมด]

ให้ทิปเจ้าของ Blog [?]
ฝากข้อความหลังไมค์
Rss Feed
Smember
ผู้ติดตามบล็อก : 85 คน [?]




Group Blog
 
All Blogs
 
Friends' blogs
[Add ศล's blog to your web]
Links
 

 
ใครขโมยเงินค่าน้ำชา

เจอโจทย์เลขข้อหนึ่งน่าสนใจ และดูเหมือนยาก แต่ก็สามารถใช้ trick นิดหน่อยก็ปัญหาได้ โจทย์ผูกเป็นเรื่องแบบนี้ครับ คณะคณิตศาสตร์มีครู 6 คน Anaximenes, Bayes, Carnot, Dirac, Euler และ Fermat มีห้องพักดื่มชา 1 ห้อง (ทางเข้า/ออก ประตูเดียว) ครูคนไหนอยากดื่มชาก็จะแวะมาห้องนี้ บริการตัวเอง พร้อมหยอดเงินใส่กระปุก ครูทั้ง 6 คนชอบดื่มชามากครับ ทุกวันต้องแวะพักดื่มชา 1 ครั้ง (และแค่ 1 ครั้งเท่านั้น) โดยเข้าไปชงชา จ่ายตังค์ และนั่งพักผ่อน อย่างที่รู้กันว่าครูคณิตศาสตร์ไม่ชอบสุงสิงกับใคร ครูทั้ง 6 คนนี้ก็เช่นกัน แต่ครูสองคนใด ๆ ในห้องดื่มชา จะมีอย่างน้อย 1 คนที่เห็นอีกคนหนึ่งเสมอ เย็นวันศุกร์ที่ผ่านมาตอนคุณเลขาไปเก็บตังค์ในกระปุก พบว่าไม่เหลือเงินเลยสักบาทเดียว วันจันทร์จึงเค้นถามครูทั้ง 6 คน ได้ความดังนี้

Anaximenes บอกว่าเห็น Bayes กับ Euler อยู่ในห้องดื่มชา
Bayes บอกว่าเห็น Anaximenes กับ Fermat อยู่ในห้องดื่มชา
Carnot บอกว่าเห็น Dirac กับ Fermat อยู่ในห้องดื่มชา
Dirac บอกว่าเห็น Anaximenes กับ Fermat อยู่ในห้องดื่มชา
Euler บอกว่าเห็น Bayes กับ Carnot อยู่ในห้องดื่มชา
Fermat บอกว่าเห็น Carnot กับ Euler อยู่ในห้องดื่มชา

มีครูคนหนึ่งที่พูดโกหก คุณคิดว่าใครครับ?

ผมลองนำโจทย์ไปถามในห้องหว้ากอ พบว่าโจทย์ไม่เคลียร์ ตรงนี้เราจะมาเคลียร์กันก่อนครับ (1) ครูแต่ละคนเข้าห้องแค่ครั้งเดียว (2) มีคนโกหกแค่คนเดียว (3) คำว่า "เห็น" หมายถึงทั้งผู้เห็นและผู้ถูกเห็นต่างก็อยู่ในห้อง (ไม่ต้องคิดกรณีเห็นจากนอกห้องครับ) (4) พูดโกหก หมายถึง สิ่งที่พูดเป็นเท็จ และถือว่าสิ่งที่ไม่พูดเป็นจริงเสมอสำหรับทุก ๆ คน เช่น A พูดว่าเห็น B กับ E เท่ากับ A ไม่เห็น C, F และ D จริง ๆ ไม่ว่า A จะพูดจริงหรือเท็จ เพราะ A ไม่ได้พูดถึง C, F, D แต่เราจะสรุปว่า A พูดเท็จเมื่อ A ไม่เห็น B หรือ A ไม่เห็น E ครับ (5) ถ้าเราเลือกครู 2 คนที่อยู่ในห้องเวลาเดียวกัน จะมีอย่างน้อย 1 คนที่เห็นอีกคนหนึ่ง ตรงนี้พูดยากครับ คุณลองสมมติตัวเองเป็นพระเจ้าที่คอยสอดส่องห้องน้ำชา ณ เวลาใด ๆ ก็ตามที่คุณเห็นว่ามีครูในห้องตั้งแต่ 2 คนขึ้นไป คุณเลือกครูในห้องนั้นขึ้นมา 2 คน (2 คนไหนก็ได้ = สองคนใด ๆ) สมมติว่าครูสองคนที่คุณเลือกมาคือ P กับ Q เงื่อนไขที่โจทย์กำหนดคือ ถ้า P ไม่เห็น Q แล้ว Q ต้องเห็น P หรือไม่ทั้ง P และ Q ต่างก็เห็นกันและกัน ถ้าเคลียร์ 5 ข้อนี้แล้วก็ลุยได้เลยครับ หลังจากย่อหน้านี้เป็นเฉลย

Anaximenes of Miletus
(ประมาณ 500 ปีก่อนคริสตกาล)
Thomas Bayes
(1702-1761)
Lazare Carnot
(1753-1823)
Paul Dirac
(1902-1984)
Leonhard Euler
(1707-1783)
Pierre de Fermat
(1601-1665)


เริ่มต้นมากำหนดสัญลักษณ์กันก่อน ให้แต่ละวงกลมแทนคน ถ้า A มองเห็น B ผมจะเขียนลูกศรชี้จาก A ไปยัง B และถ้า A กับ B อยู่ด้วยกัน มันจะเกิดเหตุการณ์ได้ 3 แบบ คือ A มองเห็น B หรือ B มองเห็น A หรือ A-B มองเห็นกันและกัน แต่ไม่ว่า 3 แบบนั้นจะเป็นยังไง ผมจะทำให้มันง่ายด้วยการลบทิศของลูกศรทิ้งเหลือเฉพาะเส้นเชื่อมระหว่างวงกลม A กับวงกลม B นั่นคือถ้ามีเส้นเชื่อม 2 คนนี้จะต้องอยู่ในห้องดื่มชาด้วยกัน ณ ช่วงเวลาใดเวลาหนึ่ง


จากนั้นเขียนแผนผังตามคำให้การของคุณครูทั้ง 6 สิ่งที่โจทย์ถามหมายความว่าในเส้นที่เห็น จะมีอย่างน้อย 1 เส้น (หรืออาจจะ 2 เส้นก็ได้) ที่ไม่ควรมีอยู่จริง เราก็แค่หาว่าเส้นไหนที่ไม่ควรมีอยู่จริง เท่านี้จะสามารถบอกได้ทันทีว่าใครโกหก


ก่อนอื่นเราลองมาพัฒนา concept ที่อาจจะเป็นประโยชน์ได้สัก 2-3 ข้อ สมมติว่ามี 3 คนอยู่ในห้องพร้อมกัน ไม่ว่าใครจะเห็นใครก็ตาม กราฟสุดท้ายต้องออกมาเป็นสามเหลี่ยม (รูปล่างซ้าย) แต่ถ้ามี 4 คนอยู่ในห้องพร้อม ๆ กันกราฟจะต้องเป็นพิระมิดฐานสามเหลี่ยม (รูปล่างกลาง, ขวา) พูดง่าย ๆ ว่าถ้ามี n คนอยู่ในห้อง แต่ละวงกลมหรือแต่ละ node จะต้องมีเส้นเชื่อม n-1 เส้นไปยังอีก n-1 node ที่เหลือเสมอ เพราะมันถูกบังคับด้วยเงื่อนไขว่าสองคนใด ๆ ก็ตามต้องมีอย่างน้อยหนึ่งคนที่เห็นอีกคน

          

ถ้าย้อนกลับไปดูในรูปที่เราวาดจากโจทย์ และถ้าทุกคนที่พูดพูดความจริง เราจะพบว่า A-B-E อยู่พร้อมหน้ากัน 3 คน, B-E-F อยู่พร้อมหน้ากัน 3 คน, E-F-C อยู่พร้อมหน้ากัน 3 คน และ D-F-C อยู่พร้อมหน้ากัน 3 คน เหตุผลที่เรามั่นใจได้เช่นนั้นเพราะแต่ละกลุ่มจับกันเป็นสามเหลี่ยม กรณีคนสามคนที่มีสองคนมองเห็นคนเดียวกันแต่ไม่อยู่พร้อมหน้ากันทั้ง 3 คน กราฟจะไม่เป็นสามเหลี่ยม เราจะได้กราฟเส้นตรง เช่น X เห็น Y และ Z เห็น Y แต่ X ไม่เห็น Z ดังรูป รูปซ้ายมือผมเขียนให้แกนนอนคือเวลา (time) นะครับ ก้อนสีชมพูทั้งสองก้อนไม่มีเวลาซ้อนทับกัน เห็นว่าถ้ามัน form เป็นสามเหลี่ยม ก้อนสีชมพูต้องมีช่วงซ้อนทับกัน


มองย้อนกลับที่รูปโจทย์อีกที เราเห็นสี่เหลี่ยม ABFD แต่ไม่มีเส้น AF กับ BD ใช่มั้ยครับ หมายความว่ามันไม่ใช่กรณีที่มี 4 คนอยู่พร้อมหน้ากัน (เพราะถ้าพร้อมหน้ากันต้องเป็นพีระมิดฐานสามเหลี่ยมตามที่ได้พูดไปแล้ว) คุณคิดว่าเป็นไปได้มั้ยที่จะเกิดรูปกราฟสี่เหลี่ยมที่มุมตรงข้ามของสี่เหลี่ยมไม่ได้เชื่อมกัน พิจารณารูปด้านล่างครับ สมมติมองเส้นตรง ABF ที่ A กับ F ไม่อยู่ด้วยกัน เราจะได้ timing เหมือน XYZ ทีนี้พอเพิ่ม D ซึ่งอ้างว่าเห็นทั้ง A และ F แต่ไม่เห็น B แปลว่า timing ของ D ต้องเป็นบริเวณสีฟ้าทั้งสองช่วง (ไม่ใช่ช่วงใดช่วงหนึ่งนะครับ) นั่นทำให้ D ต้องเข้าแล้วออกจากห้องดื่มชามากกว่าหนึ่งครั้ง กรณีนี้เราเริ่มจากเส้นตรง ABF ทำให้เห็นว่า D เกิดปัญหา ถ้าเริ่มจากเส้นอื่น เช่น BFD เราก็จะเห็นว่า A มีปัญหา ฯลฯ นั่นคือจากเงื่อนไขของโจทย์เป็นไปไม่ได้ที่เราจะเห็นวงปิดสี่เหลี่ยมที่มุมตรงข้ามไม่เชื่อมกัน


ทำนองเดียวกัน รูป 5 เหลี่ยมธรรมดา ๆ ที่มุมไม่เชื่อมกันเลย (ยกเว้นมุมที่อยู่ติดกัน) ก็เกิดขึ้นไม่ได้ครับ


ทีนี้คำตอบก็หลุดออกมาง่าย ๆ ล่ะ จากรูปโจทย์ ในกลุ่ม ABDF ต้องมีใครคนใดคนหนึ่งโกหก เพราะมันสร้างสี่เหลี่ยม ซึ่งเป็นไปไม่ได้ แปลว่าเราต้องลบออก 1 (หรือ 2) เส้น เพื่อสร้างรูปที่เป็นไปได้จาก 4 เส้นนี้ โดยที่เส้น AB ลบไม่ได้ เห็นด้วยมั้ยครับ ถ้าลบเส้นนี้ออกแปลว่ามีคนพูดโกหก 2 คน ก็เหลือเส้น BF, DF และ AD ถ้าเราลองลบเส้น DF มันจะกลายเป็นวงห้าเหลี่ยม ABFCD ซึ่งก็เป็นไปไม่ได้อีก ถ้าลบ BF กลายเป็นวง ABEFD ถึงแม้ AE จะเชื่อมกัน แต่ก็ไม่พอที่จะจัด timing ไม่ให้มีใครคนใดคนหนึ่งต้องเข้าห้องมากกว่า 1 ครั้ง ฉะนั้นเส้นที่ลบได้และทำให้กราฟที่เหลือเป็นจริงมีเพียงเส้น AD เส้นเดียวครับ การที่ D อ้างว่าเห็น A จึงเป็นเรื่องโกหก เพราะ timing ต้องบังคับให้ A กลับออกไปสอนหนังสือก่อนที่ D จะเดินเข้าห้องพักดื่มชา


Create Date : 25 มีนาคม 2553
Last Update : 4 พฤษภาคม 2553 11:02:34 น. 1 comments
Counter : 1336 Pageviews.

 
วันนี้วันเกิดคนนี้เลย


โดย: Polball วันที่: 17 สิงหาคม 2554 เวลา:8:10:57 น.  

ชื่อ : * blog นี้ comment ได้เฉพาะสมาชิก
Comment :
  *ส่วน comment ไม่สามารถใช้ javascript และ style sheet
 
 Pantip.com | PantipMarket.com | Pantown.com | © 2004 BlogGang.com allrights reserved.