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

英文解析

13. [ 8 ] How many sequences of ten binary digits are there in which neither two zeroes nor three ones everappear in a row?
    Answer: 28 Let a be the number of binary sequences of length n satisfying the conditions andnending in 0, let b be the number ending in 01, and let c be the number ending in 11. From then nlegal 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 oflength 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 nending with 01 only by adding a 1 to a sequence of length n ending in 0, so b = a . We can haven +1 na 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 nn a b cn 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.