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

["Humberto Silva Naves" <humbertonaves@xxxxxxxxxx>]

Tenho uma outra solução.

Suponha, por absurdo, que exista uma distribuição dos algarismos com no
máximo 3 algarismos distintos por linha (e por coluna).
Para cada posição do tabuleiro, marque o número de posições na mesma linha
como o mesmo algarismo.
Se a primeira linha for: 0  0  0  2  2  2  5  5  5  5
Iremos marcar:           3  3  3  3  3  3  4  4  4  4
Já que existem 3 posições com o algarismo 0, 3 com o algarismo 2 e 4 com o
algarismo 5.
A soma dos números marcados de cada coluna deverá ser menor ou igual a 3 *
10 = 30, pois temos no máximo 3 algarismos em cada coluna. Mas isso é um
absurdo, já que a soma dos números marcados de cada linha é pelo menos: 3^2
+ 3^2 + 4^2 = 34, logo a soma de todos os números marcados é pelo menos 34 *
10 = 340, portanto uma coluna deverá ter soma maior ou igual a 34.
Humberto


-----Mensagem original-----
De: owner-obm-l@mat.puc-rio.br [mailto:owner-obm-l@mat.puc-rio.br] Em nome
de Fabio Dias Moreira
Enviada em: segunda-feira, 18 de outubro de 2004 18:09
Para: obm-l@mat.puc-rio.br
Assunto: Re: [obm-l] OBM 2004 - NIVEL 3

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



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