HMMT 二月 2000 · POW 赛 · 第 16 题

HMMT February 2000 — POW Round — Problem 16

Find the n um b er of subsets A of the set of digits f 0 ; 1 ; 2 ; 3 ; : : : ; 9 g su h that A on tains no t w o onse utiv e digits. Hin t: Find a b etter statemen t of the problem; nd a re ursiv e form ula, and then attempt to solv e the problem for the n um b er of digits giv en.

解析

This is equiv alen t to nding the n um b er 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 n um b er (0-9) not b eing in the subset.) Ho w ev er, w e an't ha v e t w o onse utiv e 1's. If w e try to generalize, let 0 = A , 1 = B and w e are doing an n -letter "w ord" instead of ten. Set w = n um b er of n -letter w ords n (satisfying the onditions); set a = n um b er of w ords oun ted b y w that b egin with A; n n set b = n um b er 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 w e get the re ursiv e relationship w = w + w . Then n n 1 n n 1 n 2 w e an build up to nd that w = 144 . 10