Questão 2 Sejam n_{1}, n_{2}, \ldots, n_{m} inteiros com m ímpar. Denotemos por x=\left(x_{1}, \ldots, x_{m}\right) uma permutação dos inteiros 1,2, \ldots, m, e definamos
f(x)=x_{1} n_{1}+x_{2} n_{2}+\cdots+x_{m} n_{m} .
Verifique que existem duas permutações a e b tais que f(a)-f(b) é divisível por m !.

Passo 1

Vamos reescrever bem o que o enunciado pede. Temos m ímpar e inteiros n_{1},\dots,n_{m}. Para cada permutação
x=(x_{1},\dots,x_{m})
dos números \{1,2,\dots,m\} definimos
f(x)=x_{1}n_{1}+x_{2}n_{2}+\cdots+x_{m}n_{m}.
Queremos mostrar que há duas permutações a\neq b tais que
f(a)-f(b)\equiv 0\pmod{m!},
ou seja, f(a)\equiv f(b) módulo m!. A ideia-chave será usar um argumento de princípio da casa-dos-pombos em etapas, subindo de 2! até m! por indução.

Passo 2

Caso base: módulo 2!.
Escolha uma permutação qualquer \alpha. Defina \beta trocando em \alpha apenas os dois primeiros elementos:
\beta_{1}=\alpha_{2},\quad \beta_{2}=\alpha_{1},\quad \beta_{i}=\alpha_{i}\\ \\ (i\ge 3).
Então
f(\alpha)-f(\beta) =(\alpha_{1}-\alpha_{2})(n_{1}-n_{2}).
Como \alpha_{1},\alpha_{2} são dois números distintos em \{1,\dots,m\}, o fator \alpha_{1}-\alpha_{2} é inteiro, e n_{1}-n_{2} também. Logo
f(\alpha)-f(\beta)\equiv 0\pmod{2},
isto é, já encontramos duas permutações coincidentes módulo 2!=2.

Passo 3

Passo de indução: suponha que já construímos duas permutações a_{k}\neq b_{k} tais que
f(a_{k})\equiv f(b_{k})\pmod{k!},
e em que ambas coincidem nas posições k+1,k+2,\dots,m. Vamos usar isso para produzir a_{k+1} e b_{k+1} que coincidam módulo (k+1)! e ainda tenham o mesmo sufixo de posições k+2,\dots,m.
  1. Fixe o sufixo comum S=\{a_{k}(k+1),\dots,a_{k}(m)\}. Os primeiros k lugares em cada permutação formam uma permutação de T=\{1,\dots,m\}\setminus S, que tem exatamente k elementos.
  2. Considere todas as k+1 permutações que você obtém deixando o sufixo S fixo e permutando apenas os k primeiros elementos de todas as maneiras possíveis, mas levantando em cada caso o valor de f módulo (k+1)!.
  3. Como há k! permutações do bloco de tamanho k, mas estamos procurando colisão em (k+1)! (que tem (k+1)\cdot k! classes), o argumento de princípio da casa-dos-pombos garante que entre essas k+1 escolhas de blocos prefixos haja duas, digamos \alpha e \beta, tais que
f(\alpha)\equiv f(\beta)\pmod{(k+1)!}.
E elas, por construção, coincidem nas posições k+2,\dots,m.
4. Defina então
a_{k+1}=\alpha,\quad b_{k+1}=\beta.
Temos f(a_{k+1})\equiv f(b_{k+1})\pmod{(k+1)!} e elas são de fato permutações distintas.

Passo 4

Aplicando esse passo de indução para k=2,3,\dots,m-1, partindo do caso base k=2, chegamos finalmente a duas permutações
a_{m}\neq b_{m}
tais que
f(a_{m})\equiv f(b_{m})\pmod{m!}.

Resposta

Existem, portanto, duas permutações a e b tais que
f(a)-f(b)\equiv 0\pmod{m!}.

Exercícios relacionados