creatio ex nihilo

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

[Profile ทั้งหมด]

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




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

 
Sam Loyd's 15-Puzzle

หลายคนคงเคยเล่นเกมตัวเลื่อน 15 ตัว ในกรอบ 4 x 4 ช่องซึ่งมีช่องว่าง 1 ช่อง ที่สามารถเลื่อนตัวอื่นไปแทนที่ช่องว่างในแนว x-y ได้ จากรูปด้านล่างนี้เป็นเกมที่แซม ลอยด์ ท้าทายเอาไว้ว่าถ้าใครเลื่อนให้ตัวเลขเรียงกันได้ เอาไปเลย $1,000 (ว่ากันว่าเทียบกับเงินเดี๋ยวนี้คือ $100,000) ดูแล้วตัวเลขอยู่ตรงตำแหน่งหมดยกเว้น 14 กับ 15 ใครที่ไม่เคยลอง จะลองพยายามดูก่อนมั้ยครับ



เอาล่ะ หลังจากพยายามไปสักพักใหญ่ ๆ (หวังว่าคงไม่มีใครใช้เวลาทั้งชาติ) ก็คงจับไต๋ได้แล้วว่างานนี้แซม ลอยด์ ไม่ต้องเสียเงิน ไม่มีใครทำได้ครับ การสับเปลี่ยน (permutation) ระหว่าง 14 กับ 15 นั้นเป็นการสลับครั้งเดียว หมายความว่าถ้าคุณต้องการให้ 14 กับ 15 สลับกัน ไม่ว่าจะใช้วิธีเลื่อนซับซ้อนแค่ไหนก็ตาม คุณจะต้องใช้จำนวนคี่ครั้ง ไม่มีทางเป็นจำนวนคู่ครั้ง คุณอาจนึกภาพ 1 2 3 4 5 6 7 8 9 10 11 12 13 15 14 การสลับตำแหน่งแต่ละคู่คือการสลับ 1 ครั้ง หากผลลัพธ์ที่ต้องการคือ 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 คุณอาจสลับได้หลายแบบ เช่น แบบแรกสลับ (14,15) แบบนี้ก็ทำแค่ครั้งเดียว หรือคุณอาจจะ สลับ (13,14) จากนั้น (13, 15) คุณหยุดแค่นี้ไม่ได้ ต้องสลับ (13,14) อีก รวมแล้วเป็น 3 ครั้ง ไม่ว่าคุณจะสลับแบบไหนท่าไหนก็ตาม มันจะยังคงเป็นจำนวนคี่ครั้ง (odd permutation) แต่เงื่อนไขสำคัญในการเล่นเกมนี้คือตัวเลื่อนต้องเลื่อนสลับกับช่องว่าง และไม่ว่าคุณจะเลื่อนพิสดารตระการตายังไงก็ตาม หากสุดท้ายแล้วช่องว่างกลับมาที่เดิม คุณต้องเลื่อนจำนวนคู่ครั้ง (even permutation) เท่ากับแซม ลอยด์บอกให้คุณเลื่อนตัวเลื่อนจำนวนคู่ครั้งที่เป็นจำนวนคี่ครั้ง ใครจะไปทำได้เล่าครับ นอกจากเราจะใช้อะไรแงะตัวเลื่อนให้หลุดออกมาจากกรอบแล้วสลับที่กันบนอากาศ




Create Date : 28 กรกฎาคม 2552
Last Update : 28 กรกฎาคม 2552 13:44:16 น. 0 comments
Counter : 1518 Pageviews.

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