มดบนกระดานหมากรุก
ทุกช่องบนกระดานหมากรุกขนาด 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 น.
Counter : 1618 Pageviews.

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

Zol.BlogGang.com

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

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

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