Combinatoric

[eX]

1) ในการเดินลงบันได ต้องก้าว 10 ขั้นจึงถึงพื้น โดยมีการเดินได้ 3 แบบคือ ก้าว 1 , 2 และ 3 ขั้น
จะมีวิธีลงบันไดกี่วิธี (ลำดับการเดินสำคัญ)
2)ให้ความยาวเส้นรอบรูป 3 เหลี่ยม เป็น 5 หน่วย
ก ) ถ้าด้านทุกด้านเป็นจำนวนเต็ม จะมีสามเหลี่ยมได้กี่แบบ
ข) ถ้ามุมทุกมุมเป็นจำนวนเต็ม คำถามเดิม
ค) ถ้าทั้งมุมและด้าน เป็นจำนวนเต็ม คำถามเดิม

[gon]

ข้อ 1.
ปัญหานี้เป็นปัญหาที่อาศัย
ความสัมพันธ์เวียนบังเกิด(recurrence relation) มาช่วยคิดจะง่ายครับ

ข้อ 1 .นั้นเพื่อให้แก้ปัญหาง่ายขึ้นเรามาลอง
คิดปัญหานี้ แทน คือ บันไดมี n ขั้น
แต่วิธีการลง ลงได้ครั้งละ 1 ขั้นหรือ 2 ขั้นแทน
ถ้าให้ a_n แทน จำนวนวิธีในการเดินลงบันได n ขั้น
ดังนั้น จะได้ว่า
a₁ = 1
คือ มีขั้นเดียวก็ก้าว 1 ขั้นได้แบบเดียว
a₂ = 2
คือ มี 2 ขั้น แบบที่ 1 คือ ก้าวทีละขั้น แบบที่ 2 คือ ก้าว 2 ขั้นครั้งเดียว
a₃ = 3
คือ มี 3 ขั้น แบบที่ 1 คือ ก้าวที่ละขั้น แบบที่ 2 คือ ก้าว แบบ 1, 2 และแบบที่ 3 คือ ก้าว 2,1
a₄ = 5
คือ มี (1,1,1,1,1) (1,2,1, 1) (1,1,2,1) (1,1,1,2) และ (2,1,1,1)

ตรงนี้ให้หัดลองคิดดูแบบตรง ๆ
ต่อไปเราจะพิจารณา กรณีทั่วไป
ถ้าเราบังคับว่า ก้าวได้ทีละ 1 ขั้น หรือ 2 ขั้น สิ่งที่สำคัญคือ
การก้าวครั้งแรก ***

เราจะพบว่าการก้าวครั้งแรกนั้นทำได้ 2 วิธี คือ
กรณีที่ 1 : ครั้งแรก ก้าว 1 ขั้น
กรณีที่ 2 : ครั้งแรก ก้าว 2 ขั้น

ดังนั้นในการลงบันได n ขั้น เราแบ่งได้ 2 กรณี คือ
กรณีที่ 1 : ครั้งแรก ก้าว 1 ขั้น ดังนั้น จะเหลือบันไดอีก n-1 ขั้น
ซึ่งจะใช้วิธีในการก้าวทั้งหมด a_n-1 วิธี ถูกต้องใหมครับ.

กรณีที่ 2 : ครั้งแรก ก้าว 2 ขั้น ดังนั้น จะเหลือบันไดอีก n-2 ขั้น
ซึ่งจะใช้วิธีในการก้าวทั้งหมด a_n-2 วิธี ถูกต้องใหมครับ.

รวม 2 กรณี จึงได้ว่า a_n = a _n-1 + a_n-2
ตรงนี้ล่ะครับ เป็นความสัมพันธ์แบบ recurrence
ซึ่งจะเห็นว่า เราต้องรู้ถอยหลังอีก 2 ตัว จึงจะหาตัวต่อไปได้
เช่น ถ้า แทน n = 5 จะได้ a₅ = a ₄ + a ₃
คือจะหา a₅ ต้องรู้ค่าของ a ₄ กับ a ₃

ดังนั้น ในกรณีทั่วไป ข้อนี้นั้น เราต้องหาค่า a₁ กับ a₂ พอ
ซึ่งเราหามาในตอนต้น แล้ว (หาเกินไปถึง a₄ ไง ]

ดังนั้น เราจะได้ลำดับ
1, 2, 3, 5, 8, 13, 21, 34, 55, 89, .....
อย่างนี้ ถ้าเราตอบว่า การลงบันได 10 ขั้น โดยให้ลงได้ครั้งละ 1 หรือ 2 ขั้นจะทำได้ 89 วิธี

ถึงตรงนี้เป็นหน้าที่ของน้องหรือคนที่ต้องการแก้ปัญหาข้อนี้ซึ่งบังคับ ให้ลงได้ 1,หรือ 2 หรือ 3 ขั้น
ลองคิดปัญหานี้ดูเอง
(ตอบ 274 มั้ง)

[gon]

ข้อ 2.
ก. เหมือนกับการแก้ปัญหา x₁ + x₂ + x₃ = 5
โดยที่ x _i > 0 โดยที่ x _i เป็นจำนวนเต็ม

เรามาลองดูปัญหานี้
สมมติในร้านขายก๋วยเต๊ยวแห่งหนึ่ง
มี กระดาษมีตารางให้กรอก 3 ช่อง
ช่องแรก หมายถึง สั่งเส้นเล็ก
ช่องที่สอง หมายถึง สั่งเส้นกลาง
ช่องที่สาม หมายถึง สั่งเส้นใหญ่

ดังนั้น ถ้าเรากรอกว่า 2,3,4
หมายถึงการสั่ง เส้นเล็ก 2 ชาม เส้นใหญ่ เส้นกลาง 3 ชาม และ เส้นใหญ่ 4 ชาม
รวมสั่งทั้งหมด 9 ชาม

ถ้ามีข้อแม้ว่า ต้องสั่งชนิดละอย่างน้อย 1 ชาม ****
ปัญหานี้ก็จะเหมือนกับ การแบ่ง xxxxxxxxx : 9 ตัว
ออกเป็น 3 ส่วน โดยอาศัย เส้นตั้ง คือ | , | 2 อัน

คือ เป็น xx | xxx | xxxx

เนื่องจากมีข้อแม้ว่า ต้องสั่งชนิดละอย่างน้อย 1 ชาม ดังนั้นแบบ
|| xxxxxxxx หรือ xxxxxxxxx|| จึงไม่เกิดเป็นต้น

พิจารณา x x x x x x x x x
จะเห็นว่ามีช่องว่าง ระหว่างตัวมัน 8 ช่อง (ไม่รวม หน้าและหลังสุด)
งานที่เราต้องทำคือ การเลือกนำ แท่ง | | 2 อัน ไปใส่ในรู 8 รู
จึงทำได้ ⁸ C ₂ = (8*7) / (2)(1) = 28 วิธี

ดังนั้น ในปัญหานี้ เราจึงทำได้ 6 วิธี
แต่ ต้องตรวจสอบเงื่อนไขของ สามเหลี่ยม คือ
a + b > c เสมอ ไม่ว่า a,b,c เป็นด้านใด ๆ

ดังนั้น จริง ๆ แล้วจะเหลือ แค่ 3 วิธี คือไม่นับ กรณีเป็น
(1,3,1) (1,1,3) (3,1,1)

note. ถ้ากรณีสั่งก๋วยเตี๋ยว แบบ ไม่จำกัดเงื่อนไข จะเหมือนการเรียงสับเปลี่ยน
ของ 11 ชิ้น โดยที่ มีของซ้ำกัน 9 ชิ้น กับ 2 ชิ้น จะทำได้ 11 ! / ( 9! 2!) วิธี

[gon]

สำหรับ ข้อ 2
ข้อ ข. กับ ค. นั้น
ประการแรกโจทย์กำกวม คือ อย่าง ข.
มุมที่ว่านั้นไม่ทราบว่าเป็นมุมในหน่วยไหน
องศา หรือ เรเดียน
แต่คิดว่า แนวนี้ โจทย์น่าจะถาม เป็นองศา มากกว่า
และ ที่สำคัญ ถ้าถามเป็นองศา แล้ว ยังยึดเงื่อนไขแรกหรือไม่
ว่า เส้นรอบรูป = 5 หน่วย
ดังนั้น จึงยังไม่คิดครับ

[TOP]

ข้อ 2
ก) ควรจะได้แบบเดียวคือ 1 , 2 , 2 เท่านั้น
ข) ไม่จำเป็นต้องมีเงื่อนไขความยาวเส้นรอบรูป(ถ้าไม่จำกัดว่าต้องเป็นจำนวนเต็ม) จะเป็นเท่าไรก็ได้ (เราสามารถ normalize ได้เสมอ) โจทย์ข้อนี้จึงเหลือแค่ว่า เรามีรูปแบบของมุมในสามเหลี่ยม ที่เป็นจำนวนเต็มในหน่วยองศาได้กี่แบบ
ค) เอารูปแบบที่ซ้ำกันในข้อ ก) และ ข) มาตอบ

[gon]

เออ ใช่ จริง ๆ 3 แบบที่ว่า คือ แบบเดียวกันหมด

[eX]

ข้อ ข) หมายถึงว่า ความยาวรอบรูป 5 แล้วมุมเป็นองศาจำนวนเต็ม แต่ด้านไม่จำเป็นต้องเป็นจำนวนเต็ม
ค) หมายถึงว่า ความยาวรอบรูป 5 แล้วมุมเป็นองศาจำนวนเต็ม และ ด้านเป็นจำนวนเต็ม
แบบนี้จะมีวิธีคิดได้รึเปล่าคับ

[gon]

อ่านแล้วไม่เข้าใจหรือครับ???