โจทย์คอมบินาทอริก (ทำข้อสอบถูกผิด)

[วะฮ่ะฮ่า03]

มีข้อสอบถูกผิด 15 ข้อ ถ้าไม่มีคนทำข้อสอบติดกัน 2 ข้อเลย จะมีวิธีทำที่เป็นไปได้กี่แบบ

[gon]

ไม่มีคนทำข้อสอบติดกัน 2 ข้อเลย นี่หมายความว่า เว้นว่างไว้ก็ได้หรือครับ.

มีคนแบบนี้ในโลกด้วย

หรือว่าต้องทำทุกข้อ แต่ห้ามกาถูกติดกันสองข้อ และ ห้ามกาผิดแบบติดกันสองข้อ

ถ้าเป็นแบบแรก จะได้ $a_n = 2a_{n-1} + a_{n-2} , a_0 = 1, a_1=3$

ใช้ความสัมพันธ์เวียนเกิดหรือแก้สมการจะได้ $a_n=\frac{((1+\sqrt{2})^{n+1}+(1-\sqrt{2})^{n+1}}{2}$

ดังนั้น $a_{15 }= \frac{((1+\sqrt{2})^{16}+(1-\sqrt{2})^{16}}{2} = 665857$

[วะฮ่ะฮ่า03]

ทำทุกข้อครับ ขออภัย

[gon]

ทีแีรกผมก็ลืมคิดไป ว่าถ้าต้องทำทุกข้อ แล้วก็คงมีแค่ 2 แบบคือ

010101010101010

101010101010101

เมื่อ 0 แทน กาผิด และ 1 แทน กาถูก

ซึ่งควรจะเป็นแบบ มีบางไม่ต้องทำก็ได้เสียมากกว่า แ่ต่ข้อที่ไม่ต้องทำนี้ อาจจะไม่ทำติด ๆ กันได้

ซึ่งผมได้แก้และเพิ่มคำตอบไว้ด้านบนแล้วครับ.

[วะฮ่ะฮ่า03]

ขอบคุณคุณ gon ครับ