Quantas mensagens diferentes podem ser transmitidas em
microssegundos, usando três sinais diferentes, se um sinal requer 1 microssegundo para a transmissão e os outros dois sinais, 2 microssegundos cada um para a transmissão, e um sinal na mensagem é seguido imediatamente pelo próximo sinal?
Passo 1
O enunciado pede o número de mensagens formadas por três sinais (digamos
), em que
leva
s e
levam
s cada, de modo que a soma das durações seja
microssegundos. O conteúdo usado será contagem de sequências com restrição de soma de “pesos” e recorrência.
Passo 2
Definimos
como o número de mensagens cuja duração total é exatamente
μs. Note que:
(contém a mensagem vazia)
e
e
(só cabe o sinal
).
Passo 3
Para
, uma mensagem de duração
termina ou com um sinal de
s
, ou com um sinal de
s
ou
. Se terminar em
sobra
μs, dando
possibilidades; se terminar em
ou
sobra
μs, dando
. Logo
Passo 4
Resolvendo a recorrência via equação característica:
Assim a solução geral é
Passo 5
Usando
e
em
temos
e
. Portanto