Uma string que contém apenas 0 s, 1 s e 2 s é chamada de string ternária.
Use os itens anteriores para calcular quantas strings ternárias de extensão seis que contenham dois Os consecutivos existem.

Passo 1

Beleza, vamos entender o que a questão tá pedindo. Temos uma string ternária, que é uma sequência de 0s, 1s e 2s. Queremos saber quantas dessas strings têm exatamente seis caracteres e contêm pelo menos dois 0s seguidos, tipo “00”. Para resolver isso, vamos usar princípios de combinação e contagem, além de um pouco de lógica para evitar contar coisas duas vezes.

Passo 2

Primeiro, vamos calcular o total de possíveis strings ternárias de extensão seis. Como cada posição pode ser 0, 1 ou 2, temos 3 opções por posição. Então, o total é 3^6.

Passo 3

Agora, ao invés de contar diretamente as strings que têm dois 0s seguidos, é mais fácil calcular todas as possíveis strings de comprimento seis e subtrair aquelas que não têm nenhum par de 0s consecutivos. Isso é mais fácil de contar.

Passo 4

Para contar as strings sem dois 0s seguidos, vamos pensar em cada posição. Se uma posição não for 0, as próximas podem ser qualquer coisa. Se for 0, a próxima posição não pode ser 0. Isso é parecido com construir uma sequência onde 0s são separados por pelo menos um 1 ou 2.

Passo 5

Vamos usar uma abordagem de recorrência. Seja an o número de strings de comprimento n sem dois 0s seguidos. Para n = 1, temos 3 opções (0, 1, 2). Para n = 2, se o primeiro for 0, o segundo pode ser 1 ou 2; se for 1 ou 2, o segundo pode ser qualquer dos 3. Então, a2 = 2 + 2 times 3 = 8. Em geral, a recorrência fica:
an = an-1 times 2 + an-2 times 2
Isso considera adicionar 1 ou 2 após uma string válida de n-1 ou adicionar 0 após uma string válida de n-2.

Passo 6

Calculando os valores até n = 6:
  • a1 = 3
  • a2 = 8
  • a3 = 2 times 8 + 2 times 3 = 22
  • a4 = 2 times 22 + 2 times 8 = 60
  • a5 = 2 times 60 + 2 times 22 = 164
  • a6 = 2 times 164 + 2 times 60 = 448

Passo 7

Agora, sabemos que o total de strings ternárias de extensão seis é 3^6 = 729 e o número de strings sem dois 0s seguidos é 448. Então, o número de strings com pelo menos dois 0s seguidos é:
729 - 448 = 281

Resposta

Existem 281 strings ternárias de extensão seis que contêm dois 0s consecutivos.

Exercícios relacionados