HMMT 二月 2000 · POW 赛 · 第 16 题
HMMT February 2000 — POW Round — Problem 16
题目详情
英文原题
- Find the number of subsets A of the set of digits f 0 ; 1 ; 2 ; 3 ; : : : ; 9 g such that A on tainsnot w o onse utiv e digits. Hin t: Find a b etter statemen t of the problem; nd a re ursiv eform ula, and then attempt to solv e the problem for the number of digits giv en.
解析
英文解析
- This is equiv alen t to nding the number of sequen es of length 10 omp osed of 0's and
1's. (0 in a sp ot orresp onds to that sp ot's number (0-9) not b eing in the subset.)
Ho w ev er, we an't have t w o onse utiv e 1's. If we try to generalize, let 0 = A , 1 = Band we are doing an n -letter "w ord" instead of ten. Set w = number of n -letter w ords
(satisfying the onditions); set a = number of w ords oun ted b y w that b egin with A;nn nset b = number of w ords oun ted b y w that b egin with B. w = a + b . a = b .
n n n n n n n 1
b = w . Com bining these we get the re ursiv e relationship w = w + w . Thenn n 1 n n 1 n 2
we an build up to nd that w = 144 .
10