Uma string que contém apenas
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.
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 é
.
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
o número de strings de comprimento
sem dois 0s seguidos. Para
, temos 3 opções (0, 1, 2). Para
, 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,
. Em geral, a recorrência fica:
Isso considera adicionar 1 ou 2 após uma string válida de
ou adicionar 0 após uma string válida de
.
Passo 6
Calculando os valores até
:
Passo 7
Agora, sabemos que o total de strings ternárias de extensão seis é
e o número de strings sem dois 0s seguidos é 448. Então, o número de strings com pelo menos dois 0s seguidos é:
Resposta
Existem 281 strings ternárias de extensão seis que contêm dois 0s consecutivos.