ลองดูว่าคิดผิดตรงไหนหรือเปล่า ส่วนเรื่องเขียนให้เข้าใจคิดว่าลำบากครับ. แนะนำว่าน้องพิชญ์ควรนั่งเล่นดูก่อนนะ หาเหรียญบาทมาสัก 9 เหรียญ นั่งเล่นดู แล้วลองจดบันทึกดูว่าถ้า m = 1, n = 1 ได้อะไร ทำงี้ไปเรื่อย ๆสัก m = 3, n = 3 ก็น่าจะพอ ไม่งั้นงงแน่นอน พี่ก็ลองนั่งเล่นดูแล้วครับ.
ให้ S(m, n) แทนจำนวนหมากที่น้อยที่สุด ซึ่งเหลืออยู่บนกระดาน จากการวางหมาก m แถว และ n หลัก
จากการทดลองเราจะพบว่า S(1, 1) = 1, S(1, 2) = 1, S(1, 3) = 2, S(1, 4) = 2, S(1, 5) = 3, ... ซึ่งจะได้ว่า S(1, n) = ้n/2๙ เมื่อให้ ้x๙ แทน Ceiling function แทน จำนวนเต็มที่น้อยที่สุดที่มากกว่าเท่ากับ x เช่น ้p๙=4
ในทำนองเดียวกันจะได้ว่า S(m, 1) = ้m/2๙
จากการทดลองเดินดูจะพบว่า จะต้องเริ่มกินหมากจากตัวหมากที่อยู่ในแถวที่ 2(หรือหลักที่ 2) ไปยังตัวหมากในแถวที่ 1(หรือ หลักที่ 1) [ หรือ จะเริ่มกินจากแถวที่ m - 1 ไปยังแถวที่ m (หรือหลักที่ n - 1 ไปยังหลักที่ n ก็ได้) ]
ทีนี้เพื่อให้ตัวหมากเหลือบนกระดานน้อยที่สุด จากการลองเดินดูจะพบว่า เวลากิน จะต้องทีละทั้งหมดในแถวนั้น ๆ เช่น S(2, 2) ถ้ากินถูกวิธีจะเหลือ 1 ตัว แต่ถ้ากินผิดจะเหลือ 2 ตัว เป็นต้น.
ในการกินจะกินตามแถวไปแถว หรือ หลักไปหลักก่อน ถ้ากินถูกวิธีจะพบว่าได้คำตอบเท่ากัน
งานมี 2 ขั้นตอน
ขั้นที่ 1 . กินตามหลักก่อน
สมมติว่าจะเริ่มกินตามหลักก่อน กล่าวคือ เริ่มกินจากหลักที่ 2 ไปหลักที่ 1 จากนั้นกินจากหลัก 4 กินไปหลัก 3 ทำเช่นนี้เรื่อย ๆ ไป จะพบว่าสุดท้าย จะเหลือหลักอยู่จำนวน ้n/2๙ หลัก
(หมายเหตุ จะเริ่มจาก หลักที่ 2 ไปหลักที่ 1 พร้อม ๆ กับ กินจากหลักที่ n - 1 ไปหลักที่ n ก็ได้ เป็นต้น.)
ขั้นที่ 2. กินในแต่ละหลัก
ในแต่ะหลักที่เหลืออยู่ จะมีตัวหมากอยู่ m ตัว ซึ่งเมื่อกินในหลักนั้น ๆ ก็จะเหลือตัวหมากเท่ากับ S(m, 1) = ้m/2๙ เช่นนี้ทุกหลัก
ดังนั้น จะมีตัวหมากเหลืออยู่น้อยสุด ้n/2๙ ด ้m/2๙ ตัว บนกระดาน เช่น ถ้ามี 15 แถว 8 หลัก ก็จะเหลือหมากอยู่ ้15/2๙ ้8/2๙ = 8*4 = 32 ตัว
23 พฤษภาคม 2004 15:29 : ข้อความนี้ถูกแก้ไขแล้ว 3 ครั้ง, ครั้งล่าสุดโดยคุณ gon
|