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