Re: [obm-l] OBM 2004 - NIVEL 3

["Fabio Dias Moreira" <fabio@xxxxxxxxxxxxxxxxxxx>]

Igor Castro said:
> �! me confundi... contei 5 alg diferentes umas 10 vezes na s�tima linha
> :P mas enfim.. ok.. 4 alg diferentes sempre... essa era a resposta
> ent�o? como provar que n�o tem um quadrado com 3? 2?
> [...]

Para simplificar o argumento, eu vou dizer que uma _fila_ � uma linha ou
coluna qualquer do tabuleiro.

Lema: Se C � um conjunto de filas que cont�m todas as ocorr�ncias de um
dado algarismo, ent�o C tem pelo menos sete filas.

Prova: Suponha que |C| = k. Suponha ainda que h dessas k filas s�o
horizontais. Ent�o as dez ocorr�ncias do algarismo em quest�o devem estar
contidas na interse��es das h filas horizontais com as k-h filas
verticais, donde h(k-h) >= 10. Mas por MA-MG, h(k-h) <= [(h+k-h)/2]^2 =
k^2/4, logo k >= sqrt(40) ==> k >= 7.

Marque todas as filas que cont�m algum algarismo zero, todas as que cont�m
algum algarismo um, ... at� o nove. Pelo Lema, pelo menos 70 filas foram
marcadas; como o tabuleiro possui apenas 20 filas, o PCP implica que
alguma fila foi marcada pelo menos quatro vezes, logo esta fila possui
quatro algarismos distintos.

Unindo esta demonstra��o ao tabuleiro que o Paulo Jos� enviou para a
lista, est� demonstrado que o maior valor de n que satisfaz ao enunciado �
n=4.

[]s,

-- 
F�bio "ctg \pi" Dias Moreira


=========================================================================
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
=========================================================================