creatio ex nihilo

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

[Profile ทั้งหมด]

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




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

 
มดบนกระดานหมากรุก

ทุกช่องบนกระดานหมากรุกขนาด 9 x 9 มีมดอยู่ 1 ตัว เมื่อมีการให้สัญญาณ 1 ครั้ง มดแต่ละตัวจะเดินไปยังช่องที่ติดกันในแนวทแยงมุม (ดูรูป) ดังนั้นหลังจากเดิน 1 ครั้ง ช่องกระดานหมากรุกบางช่องอาจมีมดมากกว่า 1 ตัวและบางช่องก็อาจจะไม่มีมดอยู่เลยสักตัว จงหาค่าที่น้อยที่สุดที่เป็นไปได้ของจำนวนช่องที่ไม่มีมดหลังจากมดเดิน 1 ครั้ง



วิธีคิดที่ง่ายที่สุดคือการลงสี (coloring proof) ระบายสีตารางหมากรุกเสียใหม่ ให้คอลัมน์เดียวกันสีเดียวกันแล้วสลับสีกับคอลัมน์ที่อยู่ติดกันเหมือนทางม้าลาย ถ้าคอลัมน์แรกระบายสีดำ คอลัมน์ที่สองระบายสีขาว สาม-ดำ สี่-ขาว ห้า-ดำ หก-ขาว เจ็ด-ดำ แปด-ขาว คอลัมน์ที่เก้าระบายสีดำ

พบว่า เริ่มต้นมีมดอยู่บนช่องสีดำ 45 ตัว และมีมดอยู่บนช่องสีขาว 36 ตัว มดเดิน 1 ครั้ง มันจะต้องเปลี่ยนสีช่องเสมอ (โจทย์กำหนด) นั่นคือ มดสีขาว 36 ตัว ต้องเดินออกไปอยู่บนช่องสีดำ 45 ช่อง จึงมีอย่างน้อย 9 ช่องที่ว่าง อาจว่างมากกว่านั้นได้ แต่ว่างน้อยกว่านี้ไม่มีทางเป็นไปได้






Create Date : 10 มกราคม 2551
Last Update : 10 มกราคม 2551 1:47:27 น. 0 comments
Counter : 1585 Pageviews.

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