Questão 2 Sejam
inteiros com
ímpar. Denotemos por
uma permutação dos inteiros
, e definamos
Verifique que existem duas permutações a e b tais que
é divisível por
!.
Passo 1
Vamos reescrever bem o que o enunciado pede. Temos
ímpar e inteiros
. Para cada permutação
dos números
definimos
Queremos mostrar que há duas permutações
tais que
ou seja,
módulo
. A ideia-chave será usar um argumento de princípio da casa-dos-pombos em etapas, subindo de
até
por indução.
Passo 2
Caso base: módulo
.
Escolha uma permutação qualquer . Defina
trocando em
apenas os dois primeiros elementos:
Escolha uma permutação qualquer
Então
Como
são dois números distintos em
, o fator
é inteiro, e
também. Logo
isto é, já encontramos duas permutações coincidentes módulo
.
Passo 3
Passo de indução: suponha que já construímos duas permutações
tais que
e em que ambas coincidem nas posições
. Vamos usar isso para produzir
e
que coincidam módulo
e ainda tenham o mesmo sufixo de posições
.
- Fixe o sufixo comum
. Os primeiros lugares em cada permutação formam uma permutação de , que tem exatamente elementos. - Considere todas as
permutações que você obtém deixando o sufixo fixo e permutando apenas os primeiros elementos de todas as maneiras possíveis, mas levantando em cada caso o valor de módulo . - Como há
permutações do bloco de tamanho , mas estamos procurando colisão em (que tem classes), o argumento de princípio da casa-dos-pombos garante que entre essas escolhas de blocos prefixos haja duas, digamos e , tais que
E elas, por construção, coincidem nas posições
.
4. Defina então
4. Defina então
Temos
e elas são de fato permutações distintas.
Passo 4
Aplicando esse passo de indução para
, partindo do caso base
, chegamos finalmente a duas permutações
tais que
Resposta
Existem, portanto, duas permutações
e
tais que