2. Quante sono le sequenze di numeri di lunghezza otto composte unicamente da 0 e 1 che contengono il codice 01 ?
(A) 64
(B) 128
(C) 192
(D) 247
(E) 255
2. La risposta è (D). Il numero di stringhe di lunghezza 8 formate di cifre 0 e 1 è $2^{8}$; contiamo quelle che non contengono il codice 01 . Ci si rende facilmente conto che se una tale stringa contiene almeno uno 0 , allora tutte le cifre a destra di quello 0 sono a loro volta uguali a 0 : in caso contrario, infatti, il primo 1 che compare dopo quello 0 è necessariamente preceduto dalla cifra 0 , e abbiamo dunque trovato una sottostringa uguale a 01 . Otteniamo quindi che una stringa che non contiene il codice 01 è formata da un blocco iniziale di cifre 1 , diciamo di lunghezza $k$, seguito da un blocco di lunghezza $8-k$ di cifre 0 ; al variare di $k$ fra 0 e 8 , si ottengono le 9 stringhe della forma descritta, ovvero 11111111, 11111110, 11111100, 11111000, 11110000, 11100000, 11000000, 10000000 e 00000000 . La risposta al problema è quindi $2^{8}-9=256-9=247$.