Re: Sobre a questão número 3

["Nicolau C. Saldanha" <nicolau@xxxxxxxxxxxxxx>]

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