[obm-l] 1 a 100 em tabuleiro 10x10 Era:[obm-l] Dúvida!!

["claudio\.buffara" <claudio.buffara@xxxxxxxxxxxx>]

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