What is the maximum number of diﬀerent bit strings of length 8 you can have
without having at least 2 bit strings that start with 0000 (four 0’s)?
there is 2^8 strings of 8 bits.
there is 2^4 strings of 4 bits, so there is 2^4 strings of 8 bits that start with 0000 (each 8 bits string that start with 0000 is like a 4 bits string).
so there is 2^8-2^4+1 strings of length 8 without having at least 2 bit strings that start with 0000.