HMMT 十一月 2010 · 冲刺赛 · 第 13 题

HMMT November 2010 — Guts Round — Problem 13

[ 8 ] How many sequences of ten binary digits are there in which neither two zeroes nor three ones ever appear in a row?

解析

[ 8 ] How many sequences of ten binary digits are there in which neither two zeroes nor three ones ever appear in a row? Answer: 28 Let a be the number of binary sequences of length n satisfying the conditions and n ending in 0, let b be the number ending in 01, and let c be the number ending in 11. From the n n legal sequences of length 2 01 , 11 , 10, we find that a = b = c = 1. We now establish a recursion 2 2 2 by building sequences of length n + 1 from sequences of length n . We can add a 0 to a sequence of length n if and only if it ended with a 1, so a = b + c . We can have a sequence of length n + 1 n +1 n n ending with 01 only by adding a 1 to a sequence of length n ending in 0, so b = a . We can have n +1 n a sequence of length n + 1 ending with 11 only by adding a 1 to a sequence of length n ending in 01, so c = b . We can now run the recursion: n +1 n n a b c n n n 2 1 1 1 3 2 1 1 4 2 2 1 5 3 2 2 6 4 3 2 7 5 4 3 8 7 5 4 9 9 7 5 10 12 9 7 Our answer is then 12 + 9 + 7 = 28.