(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 2^5=32 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 a_n como o número de sequências de comprimento n sem o padrão “000”. Para construir uma sequência de comprimento n sem “000”, considere os três últimos dígitos possíveis:
  • Se ela termina em 1, há a_{n-1} opções para os n-1 primeiros dígitos.
  • Se ela termina em 01, há a_{n-2} opções para os n-2 primeiros dígitos.
  • Se ela termina em 001, há a_{n-3} opções para os n-3 primeiros dígitos.
    Não podemos terminar em “000”. Assim, temos a recorrência
a_n = a_{n-1} + a_{n-2} + a_{n-3}.

Passo 3

Precisamos de condições iniciais:
a_0 = 1,\quad a_1 = 2\\ (\text{sequências “0” e “1”}),\quad a_2 = 4\\ (\text{“00”, “01”, “10”, “11”}).ê
Agora:
a_3 = a_2 + a_1 + a_0 = 4 + 2 + 1 = 7,
a_4 = a_3 + a_2 + a_1 = 7 + 4 + 2 = 13,
a_5 = a_4 + a_3 + a_2 = 13 + 7 + 4 = 24.

Passo 4

a_5=24 sequências sem “000”. Logo, as que têm pelo menos três zeros consecutivos são
32 - 24 = 8.

Resposta

8

Exercícios relacionados