Re: Sobre a questão número 3

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

On Mon, 25 Oct 1999, Bruno Leite wrote:

> Saí da prova com a impressão de já ter visto a questão três, do 3º nível, em 
> algum lugar. Hoje, fui procurá-la e vi uma questão muito parecida, a nº 3 da 
> décima-primeira Olimpíada Iberoamericana de Matemática. Ela segue abaixo.
> 
> "Temos um tabuleiro quadriculado de k^2-k+1 linhas e k^2-k+1 colunas, onde 
> k=p+1 e p é um número primo. Para cada primo p, dê um método para distribuir 
> números 0 e 1, um número em cada casa do tabuleiro, de modo que em cada fila 
> haja exatamente k números 0 e, além disso, não haja nenhum retângulo de 
> lados paralelos aos lados do tabuleiro com números 0 em seus quatro 
> vértices."
> 
> É claro que a questão da OBM pode ser analisada de um ponto de vista 
> matricial e vai cair numa questão mais ou menos parecida com a da Ibero, com 
> a diferença que, nesta última, não teremos tabuleiros 10x10.
> 
> Eu desconheço a solução da questão da Ibero, mas se ela tiver alguma 
> semelhança com a questão da OBM, teremos uma situação injusta, pois há a 
> possibilidade de alguns alunos já irem à prova sabendo parte da solução!(ou, 
> pelo menos, poderiam aproveitar alguma idéia, etc.)
> 
> Obs.Se ela NÃO tiver semelhança com a questão da OBM, esqueçam o que eu 
> disse.
> 
> De qualquer forma, eu queria saber a resposta desta questão. Ainda não vi 
> duas pessoas que acharam a mesma resposta...

A questão da IberoAmericana de fato é bastante parecida com a da OBM, mas:

(a) a construção pedida no problema da Ibero é impossível em um tabuleiro
10x10; ou melhor, nem faz sentido, pois não existe k.

(b) o fato de 10 não ser da forma prescrit  introduz uma dificuldade extra
no problema pois é necessário tentar "aproximar" uma construção
impossível.

(c) o problema da Ibero é mais geral e mais abstrato, o da OBM mais
concreto e elementar.

Apesar de tudo isso, se alguém tivesse chamado minha atenção para a
existência deste problema em uma Ibero, eu teria votado contra a inclusão
do problema 3 na OBM. Mas ninguém que viu a prova durante a elaboração
perece ter lembrado deste problema da Ibero...
Se você procurar, você sempre encontrará algum problema parecido em algum
lugar.

A resposta correta para o problema 3 da OBM é 34. Depois eu publico a
solução.

Tentem fazer o problema da Ibero que o Bruno mencionou.
Para quem estiver interessado em um problema difícil *mesmo*:
para que valores de k a construção pedida é possível?
Em outras palavras: o problema anuncia que é possível para k = p+1, p
primo; e os outros valores de k? Por exemplo, k = 10, k = 11, ... 

[]s, N.
http://www.mat.puc-rio.br/~nicolau