> Num tabuleiro 10×10, escrevemos todos os inteiros de 1 até 100. Em > seguida, selecionamos o terceiro maior elemento de cada linha do > tabuleiro. Mostre que existe uma linha do tabuleiro tal que a soma dos > elementos nessa linha é menor ou igual a soma dos elementos > selecionados. > Desde já agradeço aos que se manifestarem!! Forte abraço a todos!! >
Seja A uma matriz (tabuleiro) 10x10 preenchida de acordo com o enunciado. S.p.d.g. (e pra facilitar a notacao) podemos supor que: i) os elementos de cada linha estao dispostos em ordem decrescente, pois isso nao altera a soma das linhas e faz com que a soma da 3a. coluna seja justamente a soma dos terceiros maiores elementos de cada linha; ii) as linhas estao dispostas de modo que a_1,3 < a_2,3 < ... < a_10,3, pois isso nao altera a soma da 3a. coluna. Seja S = a_1,3+a_2,3+...+a_10,3 = soma dos elementos da 3a. coluna. A soma de todas as entradas da matriz eh 1+2+...+100 = 5050. Assim, pelo menos uma das linhas terah soma <= 505. a_1,3 = m eh o menor elemento da 3a. coluna ==> o menor valor possivel para S eh m+(m+1)+...+(m+9) = 10m+45. Logo, se m >= 46, entao S >= 505. Eh facil ver que a_1,3 >= 8 (pois a_1,3 > a_1,4 > ... > a_1,10). Alem disso, a_2,3 >= 16, pois (a_2,3 > a_1,3 e a_2,3 > a_2,4 > ... > a_2,10). Prosseguindo desta forma, concluimos que: a_3,3 >= 24; a_4,3 >= 32; ...; a_k,3 >= 8k; ...; a_10,3 >= 80. (***) Logo, o menor valor possivel para S eh 8+16+24+...+80 = 440. Dado a_1,3 = m, o maior valor possivel para a soma da 1a. linha eh: 100+99+m+(m-1)+...+(m-7) = 8m+171. Logo, se m <= 33, entao 8m+171 <= 435 < 440. Em suma, se a_1,3 >= 46 ou a_1,3 <= 33, entao acabou. Suponhamos, portanto, que 34 <= a_1,3 = m <= 45. Isso implica que a_2,3 >= m+1, a_3,3 >= m+2, ..., a_10,3 >= m+9. Levando em conta (***) acima, podemos escrever: a_1,3 >= max(m,8) = m; a_2,3 >= max(m+1,16) = m+1; a_3,3 >= max(m+2,24) = m+2; a_4,3 >= max(m+3,32) = m+3; a_5,3 >= max(m+4,40) >= 40; a_6,3 >= max(m+5,48) >= 48; a_7,3 >= max(m+6,56) >= 56; a_8,3 >= max(m+7,64) >= 64; a_9,3 >= max(m+8,72) >= 72; a_10,3 >= max(m+9,80) >= 80. Somando tudo, obtemos S >= 4m+366. Como o maior valor possivel para a soma da 1a. linha eh 8m+171, o problema estarah resolvido se tivermos: 8m+171 <= 4m+366 <==> 4m <= 195 <==> m <= 48.75. Como estamos supondo m <= 45, acabou. []s, Claudio. ========================================================================= 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 =========================================================================