Re: [obm-l] Elevador

["Domingos Jr." <dopikas@xxxxxxxxxx>]

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, 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
=========================================================================

=========================================================================
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
=========================================================================