Re: Problemas da IMO

["Nicolau C. Saldanha" <nicolau@xxxxxxxxxxxxxxxxxxxxx>]

> > 4.
> >
> > Seja n um inteiro impar maior do que 1
> > e sejam k_1, k_2, ..., k_n inteiros dados.
> > Para cada uma das n! permutacoes a=(a_1, a_2, \dots, a_n)
> > de {1, 2, ..., n}, defina
> >
> > S(a) = \sum_{i=1}^n k_i a_i.
> >
> > Prove que existem duas permutacoes b e c, b != c,
> > tais que n! eh um divisor de S(b) - S(c).

On Wed, Jul 11, 2001 at 06:01:13AM -0300, Eduardo Casagrande Stabel wrote:

> Eu achei uma soluccao bem rapida para esse problema. Vejam se confere com a
> de voces.
> 
> Sejam {p1,p2,...,p(n!)} todas as permutaccoes de {1,2,...,n}.
> 
> Fazendo a soma direta da S de todas as permutaccoes temos
> SOMA{ S(pi) } = SOMA{ k_i }*[1+2+...+n]*[n!/n] = SOMA{ k_i }*(n+1)*n!/2,
> esse ultimo numero certamente eh divisivel por n! pois (n+1) eh par.
> 
> Supondo, por absurdo, que nao valesse o enunciado, teriamos {S(p1), S(p2),
> ..., S(p(n!))} um conjunto com todos os restos possiveis na divisao por n!,
> logo
> SOMA{ S(pi) }= 1+2+...+n! = n!(n!+1)/2 (mod n!), esse ultimo termo nao eh
> divisivel por n!, pois (n! + 1) eh impar. Chegamos a uma contradiccao.
> 
> Logo existem duas permutaccoes diferentes b e c, tal que S(b) - S(c) eh
> divisivel por n!.
> 
> Eduardo Casagrande Stabel.

Esta 'e a solu,c~ao que os l'ideres receberam originalmente com os problemas
e parece ser de longe a mais comum entre os alunos que resolveram o problema.

Existem outras, informalmente conhecidas como a solu,c~ao brasileira,
a solu,c~ao b'ulgara e a solu,c~ao russa. A solu,c~ao brasileira consiste
em contar as permuta,c~oes para as quais S(a) 'e par e 'impar e ver que
os dois n'umeros s~ao diferentes. A solu,c~ao b'ulgara 'e parecida,
prova que estes dois n'umeros s~ao diferentes, mas sem contar.
A mais simples talvez seja a solu,c~ao russa. Depois eu explico como s~ao
as tr^es.

[]s, N.