Acho que tem um jeito de mostrar que N <= 13:
Suponha N = 14
Sejam E1, ..., E7 o conjunto de andares em que os elevadores param.
Suponha, SPG, que 1 pertence a E1, E2, E3
Cada elemento deve aparecer em exatamente 3 conjuntos.
E1 - {1}, E2 - {1}, E3 - {1} tem 15 elementos no total
Devemos ter 13 elementos distintos, pois o 1� andar deve poder ser levado a
todos os demais...
Isso nos diz que h� 2 andares que s�o repetidos, ie: eles aparecem em
exatamente dois elevadores dentre {E1, E2, E3}.
Pegue um desses andares repetidos, ele se conecta com (no m�ximo) 5 + 4 = 9
andares distintos somente usando dois dos 3 primeiros elevadores, ele
precisa estar em um terceiro elevador que o conecte aos 4 (ou mais) andares
restantes...
Um fato importante � que os 4 andares restantes aparecem em um �nico
elevador de E1, E2, E3, o elevador que n�o cont�m o andar escolhido no
in�cio.
Como vamos ter que repetir esses mesmos 4 andares num outro elevador ca�mos
num problema:
Pra cada um desses andares restantes, em dois elevadores conseguimos apenas
conect�-los a 5 + 2 = 7 andares diferentes, faltam mais 6 andares pra cada
um deles, e � imposs�vel conect�-los com os nossos elevadores.
[ ]'s
On Wed, Jul 16, 2003 at 09:03:30PM -0300, [EMAIL PROTECTED] 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
=========================================================================
=========================================================================
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
=========================================================================
