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

Passo 1

O enunciado diz: há 5 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 13 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 1 lâmpada, as configurações possíveis são: ligada ( 1) ou desligada ( 0), total 2.
  • Se houver 2 lâmpadas, as configurações que não têm duas ligadas adjacentes são: 00,\;01,\;10, total 3.
    Esses exemplos já mostram que o número não cresce simplesmente como 2^n porque a restrição elimina configurações.

Passo 3

Vamos construir uma relação recursiva (uma estratégia muito útil). Defina a_n = número de configurações válidas para uma fila de n lâmpadas.
Considere a primeira lâmpada (posição mais à esquerda):
  • Se a primeira lâmpada estiver desligada ( 0), então as restantes n-1 lâmpadas podem estar em qualquer configuração válida: existem a_{n-1} opções.
  • Se a primeira lâmpada estiver ligada ( 1), então a segunda deve estar obrigatoriamente desligada ( 0) para obedecer à regra; restam então n-2 lâmpadas livres, com a_{n-2} opções.
    Somando os dois casos, obtemos a recorrência
a_n = a_{n-1} + a_{n-2}.
Essa é a mesma recorrência da sequência de Fibonacci (mas com outros valores iniciais). As bases são, como vimos,
a_1 = 2,\qquad a_2 = 3.

Passo 4

Agora calculamos passo a passo usando a recorrência:
a_3 = a_2 + a_1 = 3 + 2 = 5,
a_4 = a_3 + a_2 = 5 + 3 = 8,
a_5 = a_4 + a_3 = 8 + 5 = 13.
Portanto, pela recorrência, o número de configurações válidas para n=5 é \,13.

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 k 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 k “uns” (as lâmpadas acesas), precisamos reservar k-1 zeros mínimos entre eles. Assim, desses n lugares totais, já ocupamos k + (k-1)=2k-1 posições (contando os uns e os zeros obrigatórios entre eles). Restam n-(2k-1)=n-k+1 posições livres onde podemos “distribuir” os k blocos de umas (cada bloco corresponde a uma posição em uma sequência de n-k+1 espaços distintos). O número de maneiras de escolher quais k desses n-k+1 espaços serão ocupados é
\binom{n-k+1}{k}.
Portanto, para dado k, o número de configurações com exatamente k lâmpadas acesas e sem adjacência é \binom{n-k+1}{k}.

Passo 6

Aplicando essa fórmula para n=5: os valores possíveis de k são 0,1,2,3 (não é possível ter 4 ou 5 acesas sem adjacência).
Calculemos:
k=0:\\ \binom{5-0+1}{0}=\binom{6}{0}=1,
k=1:\\ \binom{5-1+1}{1}=\binom{5}{1}=5,
k=2:\\ \binom{5-2+1}{2}=\binom{4}{2}=6,
k=3:\\ \binom{5-3+1}{3}=\binom{3}{3}=1.
Somando:
1+5+6+1 = 13.
Obtivemos o mesmo resultado ( 13) que pela recorrência.

Passo 7

Para ver concretamente as 13 configurações, aqui estão todas como cadeias de 0 e 1 (onde 1 = lâmpada acesa, 0 = apagada):
00000,
10000,\;01000,\;00100,\;00010,\;00001,
10100,\;10010,\;10001,\;01010,\;01001,\;00101,
10101.
Conte: 1 (todas apagadas) + 5 (uma acesa) + 6 (duas acesas) + 1 (três acesas) = 13.

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 5 lâmpadas: \,13. Força aí — essa classe de contagem com “proibição de adjacência” aparece bastante em provas; decorar a ideia da recorrência a_n=a_{n-1}+a_{n-2} e a fórmula \binom{n-k+1}{k} para exatamente k acesas ajuda muito na resolução rápida.

Resposta

a) CERTO

Exercícios relacionados