creatio ex nihilo

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

[Profile ทั้งหมด]

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




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

 
coloring proofs

โดย ศล

เรียงโดมิโนขนาด 2 x 1 จำนวน 32 ตัว ลงบนตารางหมากรุกขนาด 8 x 8 ได้กี่วิธี ?



ปีพ.ศ. 2504 Michael E. Fisher นักฟิสิกส์ทฤษฎีชาวอังกฤษแสดงคำตอบสำหรับปัญหาเก่าแก่และค่อนข้างยากมากข้อนี้ว่า 12,988,816 วิธี¤ และมีคำถามต่อเนื่อง ถ้าเราตัดช่องมุมตามแนวเส้นทแยงออก 2 มุม เหลือกระดานหมากรุก 62 ช่อง จะใช้โดมิโนขนาด 2 x 1 จำนวน 31 ตัวเรียงลงบนกระดานนี้ได้กี่วิธี ดูผิวเผินเหมือนโจทย์ต่อเนื่องข้อนี้จะยากกว่าโจทย์ที่ Fisher ค้นพบคำตอบ แต่ในความเป็นจริงแล้วมันง่ายกว่าอย่างเทียบกันไม่ได้เลยทีเดียว



คำตอบคือ 0 วิธี พิสูจน์ได้ดังนี้ ถ้าเราลงสีบนกระดานหมากรุกให้ช่องที่มีด้านติดกันสีต่างกัน เราใช้สีเพียง 2 สีตามรูปที่ 1 ซึ่งพบเห็นได้บนกระดานหมากรุกปกติทั่วไป และข้อเท็จจริงของโดมิโน 1 ตัวจะต้องปิดทับช่อง 2 ช่องที่มีสีต่างกัน นั่นหมายความว่าโดมิโน 31 ตัว จะปิดทับช่องสีดำ 31 ช่อง และช่องสีขาว 31 ช่อง แต่กระดานหมากรุกตัด 2 มุมดังรูปที่ 2 มีช่องสีดำ 32 ช่อง ช่องสีขาว 30 ช่อง ดังนั้นไม่ว่าเราจะเรียงโดมิโนอย่างไรก็ไม่สามารถใช้โดมิโน 31 ตัวเรียงบนกระดานนี้ได้ การพิสูจน์แบบนี้แหละครับเรียกว่าการพิสูจน์ด้วยการลงสี หรือ Coloring Proofs





¤ รูปแบบทั่วไปของผลเฉลยปัญหาวิธีเรียงโดมิโน 2n2 ตัวลงบนตารางขนาด 2nx2n มีจำนวนวิธีเท่ากับ



รายละเอียดดูได้จาก H.N.V. Temperley, H.E. Fisher บทความ Dimer problem in statistical mechanics - an exact result. นิตยสาร Philosophical (1961)








Create Date : 03 ธันวาคม 2550
Last Update : 3 ธันวาคม 2550 15:49:13 น. 0 comments
Counter : 3391 Pageviews.

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