Exercício 21. Seja n \geqslant 1 um inteiro. Temos n lâmpadas alinhadas e numeradas, da esquerda para a direita, de 1 a n. Cada lâmpada pode estar acesa ou apagada. A cada segundo, determina-se a lâmpada apagada de maior número e inverte-se o estado desta (de acesa para apagada ou de apagada para acesa) e das lâmpadas posteriores (as lâmpadas de maior número), o processo se encerra se todas ficarem acesas.
a) Mostre que em algum momento todas as lâmpadas estarão acesas.
b) Suponha que inicialmente todas as lâmpadas estejam apagadas. Determine depois de quantos segundos todas as lâmpadas estarão acesas.
c) Suponha agora n=11 e que no início somente as lâmpadas de números 6,7 e 10 estejam acesas. Mostre que após exatamente 1997 segundos todas as lâmpadas estarão acesas.

Passo 1

O enunciado dá o seguinte processo sobre n lâmpadas numeradas de 1 (esquerda) a n (direita):
  • Cada lâmpada pode estar acesa (vou representar por 1) ou apagada (vou representar por 0).
  • A cada segundo: escolhe-se a lâmpada apagada de maior número (isto é, a mais à direita que está 0); chamaremos esse índice de i. Inverte-se o estado da lâmpada i e de todas as lâmpadas posteriores, isto é, as lâmpadas com índices i,i+1,\dots,n.
  • O processo termina quando todas as lâmpadas estiverem acesas (todas 1).
As perguntas são:
a) Mostrar que, independentemente da configuração inicial, em algum momento todas as lâmpadas ficarão acesas.
b) Se inicialmente todas as lâmpadas estão apagadas, determinar depois de quantos segundos todas ficarão acesas.
c) No caso n=11 e configuração inicial com apenas as lâmpadas de números 6,7,10 acesas, mostrar que após exatamente 1997 segundos todas ficarão acesas.

Passo 2

Vamos codificar uma configuração de lâmpadas por um número binário. Seja a configuração descrita pelos bits
(b_1,b_2,\dots,b_n),
onde b_k=1 significa que a lâmpada k está acesa e b_k=0 que está apagada. Interpreto esse vetor como um número inteiro X em base 2, com b_1 sendo o bit mais significativo (MSB) e b_n o menos significativo (LSB):
X=\sum_{k=1}^{n} b_k 2^{\,n-k}.
Exemplos simples para fixar a ideia: para n=3,
(0,0,0)\mapsto X=0,\quad (0,0,1)\mapsto X=1,\quad (1,1,1)\mapsto X=7=2^{3}-1.

Passo 3

Entender o efeito de uma operação sobre esse número X. Seja i o índice da lâmpada apagada de maior número (a mais à direita que é 0). Por definição de i, os bits à direita de i são todos 1; isto é,
b_j=1\quad\text{para todo } j>i.
A operação inverte os bits b_i,b_{i+1},\dots,b_n, ou seja, envia cada b_j para 1-b_j para j\ge i. Em particular b_i passa de 0 para 1 e os bits à direita (que eram todos 1) passam para 0.
Vamos calcular a nova representação X' depois da operação. A contribuição ao valor de X das posições j\ge i era
\sum_{j=i}^{n} b_j 2^{\,n-j}.
Como b_i=0 e b_j=1 para j>i, essa soma vale
\sum_{j=i}^{n} b_j 2^{\,n-j} = 0\cdot 2^{\,n-i} + \sum_{j=i+1}^{n} 2^{\,n-j} = \sum_{t=0}^{n-i-1} 2^{t} = 2^{\,n-i}-1.
Após inverter esses bits, a nova contribuição das posições j\ge i é
\sum_{j=i}^{n} (1-b_j) 2^{\,n-j} = 2^{\,n-i} + 0 + \cdots + 0 = 2^{\,n-i}.
Assim a diferença X'-X é
X'-X = 2^{\,n-i} - (2^{\,n-i}-1) = 1.
Portanto cada operação aumenta exatamente o número X em 1, contanto que X<2^{n}-1 (ou seja, enquanto não estivermos na configuração todas 1).

Passo 4

Interpretação prática e intuição: cada segundo corresponde a somar 1 ao número binário formado pelas lâmpadas. Começando de qualquer configuração X com 0\le X\le 2^{n}-1, a sequência de configurações segue X,X+1,X+2,\dots até atingir 2^{n}-1 (que é a configuração todas acesas). Não há ciclos antes de atingir 2^{n}-1 porque o número aumenta estritamente em 1 a cada passo enquanto não for o máximo.
Um exemplo curto para n=3 parte de 000:
000(=0)\to 001(=1)\to 010(=2)\to 011(=3)\to 100(=4)\to 101(=5)\to 110(=6)\to 111(=7),
cada etapa soma 1.

Passo 5

Concluir a parte (a). Como X aumenta de 1 em 1 e é limitado superiormente por 2^{n}-1, em número finito de passos se alcança 2^{n}-1, isto é, a configuração em que todas as lâmpadas estão acesas. Logo, independentemente da configuração inicial, em algum momento todas as lâmpadas ficarão acesas. Um limite simples para o tempo máximo é 2^{n}-1 segundos (no pior caso, começando em X=0).

Passo 6

Resolver a parte (b). Se inicialmente todas as lâmpadas estão apagadas, a configuração inicial é (0,0,\dots,0) e o número inicial é X=0. Como cada passo acrescenta 1, são necessários exatamente
2^{n}-1
segundos para chegar a X=2^{n}-1, ou seja, para que todas as lâmpadas fiquem acesas.

Passo 7

Resolver a parte (c). Agora n=11. A configuração inicial tem apenas as lâmpadas 6,7,10 acesas. Traduzindo para bits b_1,\dots,b_{11} (com b_1 MSB), temos b_6=b_7=b_{10}=1 e os outros b_k=0. O inteiro correspondente é
X=\sum_{k=1}^{11} b_k 2^{\,11-k} = 2^{\,11-6}+2^{\,11-7}+2^{\,11-10}=2^{5}+2^{4}+2^{1}.
Calcule cada potência:
2^{5}=32,\quad 2^{4}=16,\quad 2^{1}=2,
portanto
X=32+16+2=50.
O número de segundos necessários para chegar a todas acesas é
2^{11}-1 - X = 2048-1-50 = 2047-50 = 1997.
Assim, após exatamente 1997 segundos todas as lâmpadas estarão acesas.

Resposta

a) Sim — o processo atinge a configuração com todas as lâmpadas acesas; de fato cada passo aumenta em 1 o número binário correspondente, logo em no máximo 2^{n}-1 segundos chega-se a todas acesas.
b) 2^{n}-1.
c) 1997.

Exercícios relacionados