Re: Sobre a quest�o n�mero 3

["The Buddha's Son" <mocelim@xxxxxxxxxx>]

-----Mensagem original-----
De: Nicolau C. Saldanha <nicolau@mat.puc-rio.br>
Para: obm-l@mat.puc-rio.br <obm-l@mat.puc-rio.br>
Data: Quarta-feira, 27 de Outubro de 1999 20:55
Assunto: Re: Sobre a quest�o n�mero 3


>Segue a� abaixo a solu��o do problema 3;
>quem preferir n�o ver ainda por favor n�o leia al�m deste ponto.
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>On Tue, 26 Oct 1999, The Buddha's Son wrote:
>
>> >A resposta correta para o problema 3 da OBM � 34. Depois eu publico a
>> >solu��o.
>
>Numere as colunas e linhas por 0, 1, ..., 9.
>Interprete cada linha como um subconjunto Ai de {0,1,...,9}
>(as casas marcadas).
>A condi��o do enunciado se traduz da seguinte forma:
>se X � um subconjunto de {0,1,...,9} com |X| = 2
>e X � subconjunto de Ai e Aj ent�o i=j.
>
>Note que existem 45 = binom(10,2) poss�veis Xs
>(onde binom(n,m) = n!/(m! (n-m)!)).
>Como a linha i cobre binom(|Ai|,2) subconjuntos X devemos ter
>binom(|X0|,2) + binom(|X1|,2) + ... + binom(|X9|,2) <= 45
>mas desejamos maximizar
>|X0| + |X1| + ... + |X9|.
>Como a fun��o t -> binom(t,2) � convexa, devemos tomar os |Xi|
>t�o constantes quanto poss�vel. Isto corresponde � solu��o
>4 + 4 + 4 + 4 + 4 + 3 + 3 + 3 + 3 + 3 = 35
>que d� 5 * binom(4,2) + 5 * binom(3,2) = 45.
>Assim, a resposta do problema � <= 35.
>
>Vai agora o grande segredo:
>chame cada coluna de PONTO e cada linha de RETA.
>As pe�as indicam quando um ponto pertence a uma reta.
>A condi��o diz que dados dois pontos passa por eles
>no m�ximo uma reta. Assim, o problema � de geometria!
>Estamos interessados em contruir configura��es de retas e pontos.
>Uma configura��o onde por quaisquer dois pontos sempre passa uma reta
>e onde duas quaisquer retas sempre se encontram em um ponto � chamado
>plano projetivo finito.
>
>Entretanto, � imposs�vel realizar a constru��o com exatamente 35 pe�as.
>Se fosse poss�vel, ter�amos um plano projetivo
>(pois as desigualdades s�o justas)
>onde algumas retas t�m 3 e outras t�m 4 pontos.
>Mas em um plano projetivo todas as retas t�m o mesmo n�mero de pontos:
>de fato, sejam r e s duas retas e seja A um ponto que n�o pertence
>a nenhuma das duas. O ponto A cria uma bije��o entre r e s:
>dado B um ponto de r, trace a reta AB e seja B' sua interse��o com s.
>
>Finalmente, concluimos o problema mostrando que � poss�vel fazer
>a constru��o com 34 pe�as. Ajuda um pouco (mas n�o � necess�rio)
>considerar o plano projetivo de 13 elementos,
>o plano sobre o corpo {0, 1, -1} de tr�s elementos.
>Este plano �:
>
>****.........
>*...***......
>*......***...
>*.........***
>.*..*..*..*..
>.*...*..*..*.
>.*....*..*..*
>..*.*...*...*
>..*..*...**..
>..*...**...*.
>...**....*.*.
>...*.*.*....*
>...*..*.*.*..
>
>onde temos 52 pe�as em um tabuleiro 13x13.
>Se jogarmos as 3 colunas e linhas indicadas abaixo
>(3 pontos n�o colineares e as tr�s retas definidas
>por estes tr�s pontos 2 a 2):
>
>       |  ||
>       V  VV
>    ****.........
>    *...***......
>    *......***...
>    *.........***
>    .*..*..*..*..
>    .*...*..*..*.
>    .*....*..*..*
>    ..*.*...*...*
>    ..*..*...**..
>->  ..*...**...*.
>    ...**....*.*.
>->  ...*.*.*....*
>->  ...*..*.*.*..
>
>temos a solu��o com 34 pe�as:
>
>    ***.......
>    *..**.....
>    *....**...
>    *......***
>    .*.*...*..
>    .*..**..*.
>    .*....*..*
>    ..**.*...*
>    ..*.*.**..
>    ...*..*.*.
>
>> Desculpe dizer, Nicolau, mas esta quest�o foi muito mal-feita. Pela
resposta
>> que vc disse, as fichas n�o podiam formar quadrados, mas isto n�o fica
>> evidente no problema. Eu considerei que valiam quadrados e tenho
>> praticamente certeza de que acertei o problema. Mesmo eu sabendo que um
>> quadrado � um ret�ngulo, eu fiz como fiz pois se n�o valessem quadrados,
o
>> enunciado do problema deveria ser diferente. Deveria dizer:
>
>N�o posso comentar em car�ter oficial sobre crit�rios de corre��o
>pois nada foi sequer discutido mas, como opini�o pessoal minha,
>e sem qualquer compromisso quanto a crit�rios de corre��o digo o seguinte:
>nem sua interpreta��o nem as outras interpreta��es alternativas propostas
>s�o consistentes com o enunciado. Ali�s, n�o sei a resposta correta para
>a sua vers�o do problema (quadrados s�o permitidos, outros ret�ngulos s�o
>proibidos) mas a sua resposta (76, de acordo com outra mensagem)
>est� errada. Passo a demonstrar que a resposta correta n�o pode
>ser maior do que 47.
>
>Antes um conjunto X de dois elementos
>n�o podia ser subconjunto de duas linhas.
>Agora (i.e., na sua vers�o) *pode*, mas s� na seguinte condi��o:
>Se X = {a, b} e X � subconjunto de Ai e Aj ent�o vale uma das op��es:
>i = j
>i - j = a - b
>i - j = b - a
>Em particular, cada conjunto X pode ser subconjunto de no m�ximo duas
linhas.
>Assim,
>binom(|A0|, 2) + binom(|A1|, 2) + ... + binom(|A9|, 2) <= 90
>donde a melhor distribui��o �
>5 + 5 + 5 + 5 + 5 + 5 + 5 + 4 + 4 + 4
>que d�
>7 * binom(5,2) + 3 * binom(4,2) = 88.
>
>PS: O sistema que seleciona as mensagens da lista a partir de tudo
>o que chega na minha caixa de correio apresentou uma falha que faz
>com que certas mensagens n�o apare�am na minha home page.
>Acho que resolvi o problema mas por favor fiquem de olho e me avisem
>se detectarem mais falhas.
>
>http://www.mat.puc-rio.br/~nicolau


Bem,

como a minha resposta � grande e envolve muitos desenhos, � melhor eu
esperar
at� que voc� veja a minha prova. Mas n�o vi erros na forma em que eu resolvi
o problema. Sua solu��o � muito bonita, mas a minha � correta! E eu provei
que era o m�ximo!

Abra�o,

Lucas