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