(Profmat-MA12 2011) Considere o conjunto dos números escritos apenas com os algarismos 1, 2 e 3, em que o algarismo 1 aparece uma quantidade par de vezes (por exemplo, 2322 e 12123). Seja
a quantidade desses números contendo exatamente
algarismos.
(a) Liste todos esses números para
e
, indicando os valores de
e
.
(b) Explique por que
satisfaz a equação de recorrência
(a) Liste todos esses números para
(b) Explique por que
Passo 1
O enunciado pede para contar cadeias de comprimento
formadas pelos dígitos
em que o dígito 1 aparece um número par de vezes. Denotamos por
essa quantidade. Para resolver (a) listamos manualmente para
e
. Para (b) usamos um argumento de extensão de cadeias pela paridade de ocorrências de 1.
Passo 2
Para
as cadeias de um dígito são
.
Dessas, só valem as que têm número par de 1’s, ou seja, zero ocorrências de 1. Logo as válidas são
e portanto
Dessas, só valem as que têm número par de 1’s, ou seja, zero ocorrências de 1. Logo as válidas são
e portanto
Passo 3
Para
as cadeias possíveis são as 9 combinações de dois dígitos. Precisamos das que contêm 0 ou 2 ocorrências de 1.
- Com 0 ocorrências de 1: dígitos em
, ou seja . - Com 2 ocorrências de 1: apenas
.
No total são 5 cadeias, logo
Passo 4
Para deduzir a recorrência, considere todas as cadeias de comprimento
. Dessas,
têm número de 1’s par e
têm número de 1’s ímpar. Ao estender cada cadeia em mais um dígito:
- Se o prefixo tem 1’s em par (
casos), devemos não adicionar “1” (somente “2” ou “3”) para manter a paridade, gerando cadeias. - Se o prefixo tem 1’s em ímpar (
casos), só adicionar “1” corrige para par, gerando cadeias.
Somando, obtemos
Resposta
(a)
,
.
(b) Conforme o argumento de extensão,
(b) Conforme o argumento de extensão,