Questão 84 (CESP/CEBRASP-2019). As 5 lâmpadas tubulares de uma sala de aula foram instaladas formando uma única fileira. Por motivo de economia, 2 lâmpadas adjacentes nunca
poderão ficar acesas ao mesmo tempo. Assertiva: Nessa situação, há exatamente 13 configurações distintas, incluindo todas as lâmpadas desligadas, que atendem à exigência de economia.
a) CERTO b) ERRADO
poderão ficar acesas ao mesmo tempo. Assertiva: Nessa situação, há exatamente 13 configurações distintas, incluindo todas as lâmpadas desligadas, que atendem à exigência de economia.
a) CERTO b) ERRADO
Passo 1
O enunciado diz: há
lâmpadas em fila. Regra: não podem haver duas lâmpadas adjacentes acesas ao mesmo tempo. A pergunta implícita é: quantas configurações (cada lâmpada pode estar ligada ou desligada) obedecem a essa regra? A assertiva afirma que existem exatamente
configurações (contando a situação com todas desligadas). Vou contar cuidadosamente essas configurações.
Passo 2
Para criar intuição, vejamos casos pequenos:
- Se houver
lâmpada, as configurações possíveis são: ligada ( ) ou desligada ( ), total . - Se houver
lâmpadas, as configurações que não têm duas ligadas adjacentes são: , total .
Esses exemplos já mostram que o número não cresce simplesmente comoporque a restrição elimina configurações.
Passo 3
Vamos construir uma relação recursiva (uma estratégia muito útil). Defina
= número de configurações válidas para uma fila de
lâmpadas.
Considere a primeira lâmpada (posição mais à esquerda):
Considere a primeira lâmpada (posição mais à esquerda):
- Se a primeira lâmpada estiver desligada (
), então as restantes lâmpadas podem estar em qualquer configuração válida: existem opções. - Se a primeira lâmpada estiver ligada (
), então a segunda deve estar obrigatoriamente desligada ( ) para obedecer à regra; restam então lâmpadas livres, com opções.
Somando os dois casos, obtemos a recorrência
Essa é a mesma recorrência da sequência de Fibonacci (mas com outros valores iniciais). As bases são, como vimos,
Passo 4
Agora calculamos passo a passo usando a recorrência:
Portanto, pela recorrência, o número de configurações válidas para
é
.
Passo 5
Para reforçar (ou usar em prova de forma alternativa), existe também um método combinatório que conta por número de lâmpadas ligadas. Seja
o número de lâmpadas acesas. Para que não haja adjacência, entre quaisquer duas lâmpadas acesas precisa haver pelo menos uma lâmpada apagada. Se colocarmos primeiro os
“uns” (as lâmpadas acesas), precisamos reservar
zeros mínimos entre eles. Assim, desses
lugares totais, já ocupamos
posições (contando os uns e os zeros obrigatórios entre eles). Restam
posições livres onde podemos “distribuir” os
blocos de umas (cada bloco corresponde a uma posição em uma sequência de
espaços distintos). O número de maneiras de escolher quais
desses
espaços serão ocupados é
Portanto, para dado
, o número de configurações com exatamente
lâmpadas acesas e sem adjacência é
.
Passo 6
Aplicando essa fórmula para
: os valores possíveis de
são
(não é possível ter
ou
acesas sem adjacência).
Calculemos:
Calculemos:
Somando:
Obtivemos o mesmo resultado (
) que pela recorrência.
Passo 7
Para ver concretamente as
configurações, aqui estão todas como cadeias de
e
(onde
= lâmpada acesa,
= apagada):
Conte:
(todas apagadas)
(uma acesa)
(duas acesas)
(três acesas) =
.
Passo 8
Resumo do raciocínio: tanto pela recorrência quanto pelo método combinatório chegamos ao mesmo número de configurações válidas para
lâmpadas:
. Força aí — essa classe de contagem com “proibição de adjacência” aparece bastante em provas; decorar a ideia da recorrência
e a fórmula
para exatamente
acesas ajuda muito na resolução rápida.
Resposta
a) CERTO