Re: [obm-l] Olimpiadas Russas

["Domingos Jr." <dopikas@xxxxxxxxxx>]

> 102 - Prove que e possivel representar um numero natural M qualquer, M
menor
> que N! + 1, como uma soma de K numeros ( K =< N ), cada um deles divisor
de
> N! e dois a dois diferentes entre si.


realmente, é bem difícil pra 8ª série...
a minha idéia não é tão elementar, gostaria de ver a sol. da banca.

primeiramente verifique que para N=1 o enunciado é válido.

suponha que tenhamos M <= (N+1)! e queiramos obter uma soma de valor M com
divisores distintos de (N+1)!

Se M = (N+1)! nada temos a demonstrar.
Defina M_1 = M e
M_i = k_i * (N+1)!/(i+1) + M_{i+1} com 0 <= M_i < (N+1)!/i, i = 1...N

Então M = M_1 = k_1*(N+1)!/2 + M_2
note que k_1 < 2 e M_2 < (N+1)!/2.
M_2 = k_2*(N+1)!/3 + M_3
temos k_2 < 2, pois 2/3 (N+1)! > 1/2 (N+1)! > M_2

de um modo geral, k_i < 2 pois
M_i = k_i * (N+1)!/(i+1) + M_{i+1}
e 2/(i+1)  (N+1)! > 1/i  (N+1)! > M_i pois 2/(i+1) > 1/i (visto que 2i > 2i
+ 1)

dessa forma, M_{N+1} < N! e aí, por hipótese de indução, podemos obter uma
soma S, de valor M_{N+1}, apenas com divisores de N!

para cada i com k_i = 1, adicione o termo (N+1)!/i (que divide (N+1)!) à
soma S, isso dá uma soma de valor M, com fatores distintos que são todos
divisores de (N+1)!

[ ]'s

PS: note que isso fornece um algoritmo para obtermos tal soma.

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