(FUVEST-SP) Considere todas as trinta e duas sequências, com cinco elementos cada uma, que podem ser formadas com os algarismos 0 e 1. Quantas dessas sequências possuem pelo menos três zeros em posições consecutivas?
Passo 1
O enunciado pede: entre todas as
sequências binárias de comprimento 5, quantas têm pelo menos três zeros consecutivos (isto é, contêm o padrão “000”). Vamos contar seu complementar, ou seja, quantas sequências não contêm “000”, e depois subtrair de 32.
Passo 2
Defina
como o número de sequências de comprimento
sem o padrão “000”. Para construir uma sequência de comprimento
sem “000”, considere os três últimos dígitos possíveis:
- Se ela termina em 1, há
opções para os primeiros dígitos. - Se ela termina em 01, há
opções para os primeiros dígitos. - Se ela termina em 001, há
opções para os primeiros dígitos.
Não podemos terminar em “000”. Assim, temos a recorrência
Passo 3
Precisamos de condições iniciais:
Agora:
Passo 4
Há
sequências sem “000”. Logo, as que têm pelo menos três zeros consecutivos são