อ้างอิง:
|
จงหาว่าจะมีจำนวนห้าหลักทั้งหมดกี่จำนวน ที่สร้างจากเลขโดด '4', '5' และ '6' โดยที่ห้ามมี '4' สองตัวใด ๆ ติดกัน และห้ามมี '6' สองตัวใด ๆ อยู่ติดกัน
|
คำตอบของคุณ Banker ถูกต้องครับ ทีแรกผมก็จะเล่น 555 แต่สวรรค์ไม่ส่งเสริมเท่าไรนัก
ถ้าจะได้ 555..5 อาจจะต้องไปไกลเกินไป เลยลดมาเป็น 99 ก็น่าจะพอ
คือผมเห็นโจทย์ใน EMIC จะมีอยู่หลายข้อที่ถ้าใช้ ความสัมพันธ์เวียนเกิด ในการแก้ปัญหาแล้วจะทำได้ง่ายดายยิ่ง อีกทั้งแนวคิดของเรื่องนี้ ก็เข้าใจได้ไม่ยากนัก (หรือเปล่า
) ผมเลยแอบดัน(และผลัก
) วิธีการแก้โดยใช้ความสัมพันธ์เวียนเกิดอยู่เนือง ๆ โดยคาดหวังว่าจะมีคนนำไปใช้ให้เคยชินจนเป็นเรื่องปกติ สัก 1 ใน 100 ก็ยังดี แม้ว่าตามเนื้อหาหลักสูตรปกติจะอยู่ในระดับอุดมศึกษา แต่ผมคิดว่าในเฉพาะส่วนของการสร้างความสัมพันธ์นี้ให้ได้นั้น ระดับประถมขึ้นไป ก็น่าจะไปได้ (แม้ว่าอาจจะฝืดไปบ้าง)
ผมขอเฉลยดังนี้ครับ
==============================================
ให้ $a_n$ แทน จำนวนของจำนวน n หลักที่สร้างจากเลขโดด 4, 5, 6 โดยไม่มี 4 สองตัวใด ๆ ติดกัน และไม่มี 6 สองตัวใด ๆ ติดกัน
เราอาจจะแบ่งปัญหาในข้อนี้ ออกเป็น 3 กรณี คือ
กรณีที่ 1. จำนวน n หลัก ดังกล่าว ขึ้นต้นด้วย 4 ให้เขียนแทนด้วย $a_{n, 4}$
กรณีที่ 2. จำนวน n หลัก ดังกล่าว ขึ้นต้นด้วย 5 ให้เขียนแทนด้วย $a_{n, 5}$
กรณีที่ 3. จำนวน n หลัก ดังกล่าว ขึ้นต้นด้วย 6 ให้เขียนแทนด้วย $a_{n, 6}$
ดังนั้น โดยกฎการบวก เราจึงได้ว่า $$a_n = a_{n, 4} + a_{n, 5} + a_{n, 6} ... (*)$$
กรณีที่ 1. ถ้าขึ้นต้นด้วย 4
4 _ _ _ _ _ ... _
แล้วจำนวน n - 1 หลักที่เหลือ ก็จะต้องขึ้นต้นด้วย 5 หรือ 6 เท่านั้น
ซึ่งเราเขียนในรูปแบบเดียวกันได้ว่า $a_{n, 4} = a_{n-1, 5} + a_{n-1, 6}$ ... (1)
กรณีที่ 2. ถ้าขึ้นต้นด้วย 5
5 _ _ _ _ _ ... _
แล้วจำนวน n - 1 หลักที่เหลือ ก็จะต้องขึ้นต้นด้วยอะไรก็ได้ ไม่ว่าจะเป็น 4, 5, 6 นั่นก็คือ $a_{n, 5} = a_{n-1}$ ... (2)
กรณีที่ 3. ถ้าขึ้นต้นด้วย 6
6 _ _ _ _ _ ... _
แล้วจำนวน n - 1 หลักที่เหลือ ก็จะต้องขึ้นต้นด้วย 4 หรือ 5 เท่านั้น
ซึ่งเราเขียนในรูปแบบเดียวกันได้ว่า $a_{n, 6} = a_{n-1, 4} + a_{n-1, 5}$ ... (3)
แทนค่าจากสมการ (1), (2), (3) ลงในสมการ (*) จะได้ $$a_n = a_{n-1, 5} + a_{n-1, 6} + a_{n-1} + a_{n-1, 4} + a_{n-1, 5}$$ $$a_n = (a_{n-1, 4} + a_{n-1, 5} + a_{n-1, 6}) + a_{n-1} + a_{n-1, 5}$$ผลรวมในวงเล็บนั้น เราประยุกต์ซ้ำเหมือนสมการ (*) แต่ย้อนจากขวาไปซ้ายได้เป็น $$a_n = a_{n-1} + a_{n-1}+ a_{n-1, 5}$$$$a_n = 2a_{n-1} + a_{n-1, 5}$$และจากสมการ (2) แสดงว่า $a_{n-1, 5} = a_{n-2}$ (หรือจะใช้ความเข้าใจก็ได้)
ดังนั้น
$$a_n = 2a_{n-1}+a_{n-2}$$
และเนื่องจาก
จำนวนหนึ่งหลัก ตามเงื่อนไขได้แก่ 4, 5, 6 นั่นคือ $a_1 = 3$
จำนวนสองหลัก ตามเงื่อนไขได้แก่ 45, 46, 54 55, 56, 64, 65 นั่นคือ $a_2 = 7$
ดังนั้น $a_3 = 2a_2 + a_1 = 2(7) + 3 = 17$
$a_4 = 2a_3 + a_2 = 2(17) + 7 = 41$
$a_5 = 2a_4 + a_3 = 2(41) + 17 = 99$