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: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED] Em nome de Fabio Dias Moreira Enviada em: segunda-feira, 18 de outubro de 2004 18:09 Para: [EMAIL PROTECTED] 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 =========================================================================
