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 <[EMAIL PROTECTED]> 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" > <[EMAIL PROTECTED]>: > > > >========================================================================= > >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 =========================================================================
