Re: [obm-l] Elevador

[Carlos Yuzo Shine <cyshine@xxxxxxxxx>]

Gente,

O que escrevi antes não ajuda muito no problema dos
elevadores. Eu pensei mais seriamente nele e provei
que as únicas soluções são obtidas assim: separe os 14
andares em 7 pares de andares. Tome-os como pontos do
plano heptaprojetivo P2(Z/2Z). Os elevadores
correspondem às retas (que contêm cada uma 3 pares, ou
seja, 6 andares).

Para provar isso, pense nos seguintes lemas:

Lema 1: Cada andar é atendido por exatamente 3
elevadores.

Lema 2: Dois elevadores distintos atendem a exatamente
2 andares em comum.

Lema 3: Considere os três elevadores que atendem um
determinado andar. Então esses três elevadores atendem
um outro andar em comum.

Lema 4: Há 7 pares de andares, cada um atendido por
mais de um elevador (no caso, três). Os pares são
disjuntos e cada andar está contido em exatamente um
par.

Lema 5: Os 7 pares podem ser vistos como pontos e os
elevadores, como retas em P2(Z/2Z).

Dicas: eu usei contagem dupla para os lemas 1 e 2. Nos
lemas 2 e 3 usei argumentos a la casa dos pombos. O
lema 4 saiu por indução e o lema 5 decorre dos lemas
anteriores.

Há 14!/[7!(2!)^7] maneiras de particionar os andares e
151200 maneiras de distribuir os 7 pontos em 7 retas
do plano heptaprojetivo (veja o livro do Morgado de
Combinatória e Probabilidade que tem o seguinte
problema: um professor, para se despedir de seus 7
alunos, resolveu pagar 7 jantares, cada um para 3
alunos, de modo que cada par de alunos apareça no
máximo em um mesmo jantar. De quantas maneiras podemos
organizar os jantares?), assim há
151200*14!/[7!(2!)^7] = 20432412000 soluções (que no
fundo, são essencialmente uma só).

[]'s
Shine

> >     Oi Nicolau,
> > >     Acho que consegui uma solucao com 14
> andares:
> > e´ que P:=P2(Z/(2)) tem 7
> > >elementos e 7 retas (seja R o conjunto de suas
> > retas). Tomamos como conjunto
> > >dos andares Px{0,1}, e como conjunto dos
> elevadores
> > a diagonal de RxR.
> > >Da´ para escrever mais explicitamente isso: os
> > andares sao 1,2,...,14.
> > >Os elevadores sao
> > {1,2,3,8,9,10},{1,4,5,8,11,12},{1,6,7,8,13,14},
> > >{2,4,6,9,11,13},{2,5,7,9,12,14},{3,4,7,10,11,14}
> e
> > {3,5,6,10,12,13}.
> > >     Abracos,
> > >              Gugu
> > >
> > >Citando "Nicolau C. Saldanha"
> > <nicolau@sucuri.mat.puc-rio.br>:
> > >
> >
>
>=========================================================================
> > >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
> >
>
=========================================================================
> 
> 
> __________________________________
> Do you Yahoo!?
> SBC Yahoo! DSL - Now only $29.95 per month!
> http://sbc.yahoo.com
>
=========================================================================
> 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
>
=========================================================================


__________________________________
Do you Yahoo!?
SBC Yahoo! DSL - Now only $29.95 per month!
http://sbc.yahoo.com
=========================================================================
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
=========================================================================