เตรียมสอบ สพฐ. 2555 เรื่องการนับ

[polsk133]

ผมคิดว่า แผนภาพต้นไม้น่าจะง่ายสุดแล้วแหละครับ อยู่ที่ว่านับถูกหรือไม่

[gon]

จงหาว่าจะมีจำนวนห้าหลักทั้งหมดกี่จำนวน ที่สร้างจากเลขโดด '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$

[polsk133]

เป็นวิธีที่เจ๋งมากครับ พอจะมีโจทย์ประมาณนี้อีกไหมครับ

[gon]

ข้อความเดิมเขียนโดยคุณ polsk133

เป็นวิธีที่เจ๋งมากครับ พอจะมีโจทย์ประมาณนี้อีกไหมครับ

จัดไป 2 ข้อครับ. ถ้าเข้าใจแล้ว สองข้อนี้ก็เรียกว่าง่ายเกินห้ามใจ

(03/03/2555-01) จงหาว่าจะมีจำนวนห้าหลักทั้งหมดกี่จำนวน ที่สร้างจากเลขโดด '4', '5', '6' และ '7 'โดยที่
ห้ามมี '4' สองตัวใด ๆ ติดกัน และ
ห้ามมี '6' สองตัวใด ๆ อยู่ติดกัน และ
ห้ามมี '7' สองตัวใด ๆ อยู่ติดกัน

(03/03/2555-02) จงหาว่าจะมีจำนวนห้าหลักทั้งหมดกี่จำนวน ที่สร้างจากเลขโดด '4', '5', '6' และ '7 'โดยที่
ห้ามมี '4' สองตัวใด ๆ ติดกัน และ
ห้ามมี '7' สองตัวใด ๆ อยู่ติดกัน

[polsk133]

ข้อแรกได้469 อะครับผมไดิว่า
$a_n=3(a_{n-1})+a_{n-2}$

ปลขอบคุณมากครับสำหรับวิธีแบบนี้

เพิ่มอีกข้อ. ผมได้634 คิดได้ว่า $a_n=3(a_{n-1})+2(a_{n-2})$

[gon]

ข้อความเดิมเขียนโดยคุณ polsk133

ข้อแรกได้469 อะครับผมไดิว่า
$a_n=3(a_{n-1})+a_{n-2}$

ปลขอบคุณมากครับสำหรับวิธีแบบนี้

เพิ่มอีกข้อ. ผมได้634 คิดได้ว่า $a_n=3(a_{n-1})+2(a_{n-2})$

แจ่มมากครับ.

จัดให้อีกโดยไม่ต้องขอ

ถ้าสนใจจะปวดหัวต่อก็ลองคิดดูได้นะครับ.

(03/03/2555-03)
จงหาว่าจะมีจำนวนห้าหลักทั้งหมดกี่จำนวน ที่สร้างจากเลขโดด '4' และ '5' โดยที่มี '5' ติดกันอย่างน้อย 2 ตัวขึ้นไป

และจงหาความสัมพันธ์เวียนเกิดของจำนวน n หลัก ที่สร้างจากเลขโดด '4' และ '5' โดยที่มี '5' ติดกันอย่างน้อย 2 ตัวขึ้นไปด้วย

(03/03/2555-04)
จงหาว่าจะมีจำนวนห้าหลักทั้งหมดกี่จำนวน ที่สร้างจากเลขโดด '4' , '5' และ '6' โดยที่มี '5' ติดกันอย่างน้อย 2 ตัวขึ้นไป

และจงหาความสัมพันธ์เวียนเกิดของจำนวน n หลัก ที่สร้างจากเลขโดด '4' , '5' และ '6' โดยที่มี '5' ติดกันอย่างน้อย 2 ตัวขึ้นไปด้วย

[polsk133]

ข้อแรกไม่ค่อยมั่นใจครับ
ผมได้ว่า $a_n=a_{n-1}+a_{n-2}$

ข้อสองได้ $a_n=2a_{n-1}+a_{n-2}$

[gon]

ข้อความเดิมเขียนโดยคุณ polsk133

ข้อแรกไม่ค่อยมั่นใจครับ
ผมได้ว่า $a_n=a_{n-1}+a_{n-2}$

ข้อสองได้ $a_n=2a_{n-1}+a_{n-2}$

ไม่ใช่ทั้งสองข้อครับ. ผมทำให้ดูข้อแรกละกัน

ให้ $a_n$ แทนจำนวนของจำนวน n หลักที่สร้างจากเลขโดด '4', '5' โดยที่ไม่มี '5' สองตัวใด ๆ ติดกัน
ให้ $b_n$ แทนจำนวนของจำนวน n หลักที่สร้างจากเลขโดด '4', '5' โดยที่มี '5' ติดกันอย่างน้อยสองตัวขึ้นไป
จะได้ว่า $a_n + b_n = 2^n $ ... (*)

ดังนั้น $b_n = 2^n - a_n$

แต่เนื่องจากเราทราบว่า $a_n = a_{n-1} + a_{n-2}$
ดังนั้น $b_n = 2^n - (a_{n-1} + a_{n-2})$ ... (**)

แต่จากสมการ (*) เราได้ว่า $a_n = 2^n - b_n$ ประยุกต์สมการนี้กับสมการ (**) จะได้

$b_n = 2^n - (2^{n-1} - b_{n-1} + 2^{n-2} - b_{n-2})$

ดังนั้น $b_n = b_{n-1} + b_{n-2} + 2^{n-2}$ โดยที่ $b_1=0, b_2 = 1$ เป็นความสัมพันธ์เวียนเกิดที่ต้องการ

[gnap]

ข้อความเดิมเขียนโดยคุณ gon

ไม่ใช่ทั้งสองข้อครับ. ผมทำให้ดูข้อแรกละกัน

ให้ $a_n$ แทนจำนวนของจำนวน n หลักที่สร้างจากเลขโดด '4', '5' โดยที่ไม่มี '5' สองตัวใด ๆ ติดกัน
ให้ $b_n$ แทนจำนวนของจำนวน n หลักที่สร้างจากเลขโดด '4', '5' โดยที่มี '5' ติดกันอย่างน้อยสองตัวขึ้นไป
จะได้ว่า $a_n + b_n = 2^n $ ... (*)

ดังนั้น $b_n = 2^n - a_n$

แต่เนื่องจากเราทราบว่า $a_n = a_{n-1} + a_{n-2}$
ดังนั้น $b_n = 2^n - (a_{n-1} + a_{n-2})$ ... (**)

แต่จากสมการ (*) เราได้ว่า $a_n = 2^n - b_n$ ประยุกต์สมการนี้กับสมการ (**) จะได้

$b_n = 2^n - (2^{n-1} - b_{n-1} + 2^{n-2} - b_{n-2})$

ดังนั้น $b_n = b_{n-1} + b_{n-2} + 2^{n-2}$ โดยที่ $b_1=0, b_2 = 1$ เป็นความสัมพันธ์เวียนเกิดที่ต้องการ

ขอบคุณมากครับ

[pond=w=]

ขอบคุณค่ะ