Exercício 21. Seja
um inteiro. Temos
lâmpadas alinhadas e numeradas, da esquerda para a direita, de 1 a
. 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
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.
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
Passo 1
O enunciado dá o seguinte processo sobre
lâmpadas numeradas de
(esquerda) a
(direita):
- Cada lâmpada pode estar acesa (vou representar por
) ou apagada (vou representar por ). - A cada segundo: escolhe-se a lâmpada apagada de maior número (isto é, a mais à direita que está
); chamaremos esse índice de . Inverte-se o estado da lâmpada e de todas as lâmpadas posteriores, isto é, as lâmpadas com índices . - O processo termina quando todas as lâmpadas estiverem acesas (todas
).
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 e configuração inicial com apenas as lâmpadas de números
acesas, mostrar que após exatamente
segundos todas ficarão acesas.
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
Passo 2
Vamos codificar uma configuração de lâmpadas por um número binário. Seja a configuração descrita pelos bits
onde
significa que a lâmpada
está acesa e
que está apagada. Interpreto esse vetor como um número inteiro
em base 2, com
sendo o bit mais significativo (MSB) e
o menos significativo (LSB):
Exemplos simples para fixar a ideia: para
,
Passo 3
Entender o efeito de uma operação sobre esse número
. Seja
o índice da lâmpada apagada de maior número (a mais à direita que é
). Por definição de
, os bits à direita de
são todos
; isto é,
A operação inverte os bits
, ou seja, envia cada
para
para
. Em particular
passa de
para
e os bits à direita (que eram todos
) passam para
.
Vamos calcular a nova representação
depois da operação. A contribuição ao valor de
das posições
era
Como
e
para
, essa soma vale
Após inverter esses bits, a nova contribuição das posições
é
Assim a diferença
é
Portanto cada operação aumenta exatamente o número
em
, contanto que
(ou seja, enquanto não estivermos na configuração todas
).
Passo 4
Interpretação prática e intuição: cada segundo corresponde a somar
ao número binário formado pelas lâmpadas. Começando de qualquer configuração
com
, a sequência de configurações segue
até atingir
(que é a configuração todas acesas). Não há ciclos antes de atingir
porque o número aumenta estritamente em
a cada passo enquanto não for o máximo.
Um exemplo curto para
parte de
:
cada etapa soma
.
Passo 5
Concluir a parte (a). Como
aumenta de
em
e é limitado superiormente por
, em número finito de passos se alcança
, 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 é
segundos (no pior caso, começando em
).
Passo 6
Resolver a parte (b). Se inicialmente todas as lâmpadas estão apagadas, a configuração inicial é
e o número inicial é
. Como cada passo acrescenta
, são necessários exatamente
segundos para chegar a
, ou seja, para que todas as lâmpadas fiquem acesas.
Passo 7
Resolver a parte (c). Agora
. A configuração inicial tem apenas as lâmpadas
acesas. Traduzindo para bits
(com
MSB), temos
e os outros
. O inteiro correspondente é
Calcule cada potência:
portanto
O número de segundos necessários para chegar a todas acesas é
Assim, após exatamente
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
o número binário correspondente, logo em no máximo
segundos chega-se a todas acesas.
b) .
c) .
b)
c)