HMMT 二月 2007 · GEN2 赛 · 第 8 题

HMMT February 2007 — GEN2 Round — Problem 8

[ 5 ] Compute the number of sequences of numbers a , a , . . . , a such that 1 2 10 I. a = 0 or 1 for all i i II. a · a = 0 for i = 1 , 2 , . . . , 9 i i +1 III. a · a = 0 for i = 1 , 2 , . . . , 8 . i i +2

解析

[ 5 ] Compute the number of sequences of numbers a , a , . . . , a such that 1 2 10 I. a = 0 or 1 for all i i 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 length n n . 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 n if 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 n so there are A of them. We thus obtain the recursive relation A = A + A . Note that n − 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