HMMT 二月 2007 · GEN2 赛 · 第 8 题

英文解析

8. [ 5 ] Compute the number of sequences of numbers a , a , . . . , a such that
   1 2 10
   I. a = 0 or 1 for all ii
   II. a · a = 0 for i = 1 , 2 , . . . , 9
   i i +1
   III. a · a = 0 for i = 1 , 2 , . . . , 8 .
   i i +2
   Answer: 60 . Call such a sequence “good,” and let A be the number of good sequences of lengthnn . Let a , a , . . . , a be a good sequence. If a = 0, then a , a , . . . , a is a good sequence if and only
   1 2 n 1 1 2 nif a , . . . , a is a good sequence, so there are A of them. If a = 1, then we must have a = a = 0,
   2 n n − 1 1 2 3
   and in this case, a , a , . . . , a is a good sequence if and only if a , a , . . . , a is a good sequence,
   1 2 n 4 5 nso there are A of them. We thus obtain the recursive relation A = A + A . Note thatn − 3 n n − 1 n − 3
   A = 2 , A = 3 , A = 4 . Plugging these into the recursion eventually yields A = 60 .
   1 2 3 10