Re: [obm-l] Elevador

[Carlos Yuzo Shine <cyshine@xxxxxxxxx>]

Oi, Gugu e demais membros da lista!

De fato, parece que o problema dos elavadores está
relacionado com o problema da loteria da transylvania,
que vi na página

http://mathworld.wolfram.com/FanoPlane.html

Veja um trecho de lá:

The Fano plane also solves the transylvania lottery,
which picks three numbers from the integers 1-14.
Using two Fano planes we can guarantee matching two by
playing just 14 times as follows. Label the graph
vertices of one Fano plane by the integers 1-7, the
other plane by the integers 8-14. The 14 tickets to
play are the 14 lines of the two planes. Then if
(a,b,c) is the winning ticket, at least two of a,b,c
are either in the interval [1, 7] or [8, 14]. These
two numbers are on exactly one line of the
corresponding plane, so one of our tickets matches
them.

O plano de Fano é o plano P2(Z/2Z) que o Gugu falou, e
é o plano projetivo finito baseado em Z/2Z. No link
acima está tudo explicadinho. Você pode ler mais sobre
isso na Eureka! 15, no meu artigo sobre planos
projetivos.

O que está acima não resolve completamente o problema
dos elevadores, só garante que 14 elevadores, cada um
parando em no máximo 3 andares, são suficientes para
atender o problema de dois prédios, cada um com 7
andares (seriam 7 elevadores em cada prédio). O que o
Gugu fez foi "juntar" pares de dois dos 14 elevadores,
um de cada prédio (de fato, ele juntou os pares
(a,b,c) e (a+7,b+7,c+7), a,b,c <= 7). De a <=7 podemos
ir para qualquer andar <=7 (por causa das ternas
(a,b,c) do primeiro plano projetivo) e para qualquer
andar >=8 (é só ir para a+7 e depois de lá dá para ir
para qualquer andar >=8, por causa das ternas do
segundo plano projetivo).

Eu sei que há 168 automorfismos em P2(Z/2Z) que mantêm
colinearidade (isto é, há 168 maneiras de numerarmos
os pontos de P2(Z/2Z) de modo que as retas sejam
sempre {1,2,3}, {1,4,5}, {1,6,7}, {2,4,6}, {2,5,7},
{3,5,6} e {3,4,7}). Isso geraria 168 permutações para
o primeiro plano projetivo. O problema 5 da OPM 2001
pede exatamente para calcular esse 168. Veja em

http://www.opm.mat.br/provas/fase_final_2001.pdf

Há também 7! maneiras de fazermos os pares de ternas
(basta associarmos cada ponto do primeiro plano
projetivo a um ponto diferente do segundo plano
projetivo, o que seria o número de bijeções de
{1,2,3,4,5,6,7} em {8,9,10,11,12,13,14}). Assim, há
pelo menos 168*7! = 846720 soluções.

Além disso, não há nada de especial em {1,2,3,4,5,6,7}
e {8,9,10,11,12,13,14}; podemos escolher outras
partições de [14]. Mas acho que isso pode gerar
repetições na nossa contagem, então não me arrisco a
multiplicar tudo por metade de 14 escolhe 7.

Além disso, não sei se há outras soluções e se dá para
contá-las de jeito bonitinho...

Espero não ter cometido nenhum erro.

[]'s
Shine

--- Carlos Gustavo Tamm de Araujo Moreira
<gugu@impa.br> wrote:
>   Caro Domingos,
>   Voce pode esquecer as minhas tres primeiras
linhas: elas so' servem como explicacao de como eu
cheguei a essa solucao (e alias nao estao bem
escritas: eu devia ter dito que o conjunto dos
elevadores (ou, mais propriamente, o conjunto dos
conjuntos de andares nos quais para cada elevador) e'
{(rx{0})U(rx{1}), r em R}).
>   Nas tres linhas seguintes eu descrevo uma solucao
explicita com 14 andares, listando os conjuntos de
andares em que para cada elevador. Essa solucao nao e'
unica: dada qualquer permutacao de {1,2,...,14},
podemos aplicar essa permutacao a todos os elementos
de todos os conjuntos que eu listei e obter outra
solucao. Isso da' muitas solucoes (mas nao sei se e'
possivel classificar todas asd solucoes de um jeito
simples usando esse tipo de equivalencia).
>   Abracos,
>            Gugu
>  
> >
> >Não entendi quase nada do que você falou, mas
> percebi o meu erro:
> >
> >"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}."
> >
> >Eu acabei negligenciando o caso em que não há dois
> andares repetidos, mas
> >apenas 1 que aparece nos 3 elevadores.
> >
> >A propósito, essa é a única solução com N = 14?
> >
> >[ ]'s
> >
> >--- x ---
> >
> >     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
=========================================================================