instant Insanity
ประมาณปี 1965 นาย Frank Armbruster ประดิษฐ์กลปริศนา Instant Insanity (สามารถขายได้ถึง 12 ล้านชิ้นในช่วงปี 1966-67) กล่องลูกบาศก์ 4 กล่อง แต่ละหน้าของแต่ละกล่องเป็นสีใดสีหนึ่งใน 4 สี จุดหมายของเกมนี้คือต่อซ้อนกล่องเป็นคอนโด 4 ชั้น ให้แต่ละด้านของคอนโดทั้ง 4 ด้าน มีสีแต่ละชั้นไม่ซ้ำกัน (1 สีปรากฏได้แค่ชั้นใดชั้นหนึ่งต่อ 1 ด้าน)



Tom Davis อดีตนักวิทยาศาสตร์ที่ Silicon Graphics เคยบรรยายเด็กนักเรียนระดับมัธยมในโครงการ Mathematical Circles 3 ครั้ง (ที่ Berkeley, San Jose และ Palo Alto) ในเอกสารประกอบการสอนเรื่องหนึ่ง เขามีโจทย์ปัญหาถามนักเรียนเกี่ยวกับปริศนา Instant Insanity



จากรูปเป็นภาพคลี่ของกล่องลูกบาศก์ 4 กล่อง W แทนสี ขาว, R แทนสี แดง, B แทนสี ฟ้า, G แทนสี เขียว เขาให้นักเรียนของเขาหาวิธีต่อกล่องเพื่อให้ได้คอนโด 4 ชั้น ซึ่งทั้ง 4 ด้านต้องมีครบทั้ง 4 สี ลองคิดเล่น ๆ ก่อนดูเฉลยนะครับ

เฉลย ข้อนี้เราใช้ความรู้เรื่องกราฟมาช่วยแก้ปัญหาได้ ดูจากรูปภาพคลี่กล่องแล้วนำมาเขียนกราฟ ใช้หมายเลข 1-4 แทนกล่องที่ 1-4 โดย node ของกราฟแสดงสี 4 สี (จึงมี 4 nodes) และ edge เชื่อมระหว่างสีของด้านตรงกันข้าม สิ่งที่เราต้องการคือ 2 sub graphs ที่มี 4 nodes 4 edges 4 หมายเลขไม่ซ้ำกัน โดยแต่ละ node มี 2 edges และทั้ง 2 sub graphs ไม่ใช้ edge ร่วมกัน แล้วใช้ sub graph อันแรกเรียงกล่องสีด้านหน้าด้านหลัง sub graph อีกอันจะเป็นสีด้านซ้าย-ขวา



เช่น
sub graph 1: G-4-W-1-B-3-R-2-G
sub graph 2: R-4-G-3-W-2-B-1-R

ได้ผลลัพธ์คือ
กล่อง 1: W B B R (อาจเรียง หน้า หลัง ซ้าย ขวา ก็ได้ โดย 2 ตัวแรก และ 2 ตัวหลังเป็นด้านตรงข้ามกัน)
กล่อง 2: R G W B
กล่อง 3: B R G W
กล่อง 4: G W R G





Create Date : 29 เมษายน 2551
Last Update : 29 เมษายน 2551 16:05:34 น.
Counter : 2150 Pageviews.

0 comments
ชื่อ : * blog นี้ comment ได้เฉพาะสมาชิก
Comment :
 *ส่วน comment ไม่สามารถใช้ javascript และ style sheet
 

Zol.BlogGang.com

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

[ดู Profile ทั้งหมด]
 ผู้ติดตามบล็อก : 85 คน [?]

บทความทั้งหมด