[obm-l] Elevador

["Nicolau C. Saldanha" <nicolau@xxxxxxxxxxxxxxxxxxxxx>]

On Wed, Jul 16, 2003 at 09:03:30PM -0300, jorgeluis@edu.unifor.br wrote:
> Num prédio de apartamentos há 7 elevadores que param
> em não mais que 6 andares. 
> É possível ir de um andar a qualquer outro sem trocar de elevador. Qual é o 
> número máximo de andares que esse prédio pode ter?   (RPM/IME/USP)

O problema est bem legal. Ainda nao completei uma solucao mas vou mandar
meus resultados parciais.

N <= 14

De fato, temos no maximo 42 paradas (uma parada est um par (i,j) onde
i est um andar, j est um elevador, e o elevador j para no andar i).
Se N > 11 devemos ter pelo menos tres paradas por andar
(pois duas paradas nos dao apenas dois elevadores que atingem
no maximo 10 outros andares). Assim 3N <= 42 e N <= 14.

N >= 12

Basta observar a configuracao abaixo onde um + indica que o elevador
para naquele andar e um . indica que ele nao para. Os andares estao 
um em cima do outro, claro, e os elevadores um ao lado do outro.
Observe que 6 elevadores foram suficientes.

+++...
+++...
+++...
+..++.
+..++.
+..++.
.+.+.+
.+.+.+
.+.+.+
..+.++
..+.++
..+.++

Eu fiz uns diagramas e me convenci que N <= 13 mas a prova foi
meio bracal, no caso a caso, e pode estar errada.

[]s, N.

=========================================================================
Instruções para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
=========================================================================