Seja N ímpar. Provar que para qualquer bijeção p: IN IN do conjunto IN=1,2, ldots, N, o produto
P(p)=(1-p(1))(2-p(2)) cdots(N-p(N))
é necessariamente par.
Dica: O produto de vários fatores é par se, e somente se, um dos fatores é par.

Passo 1

Beleza, então o enunciado diz: “Seja P(p);=;(1-p(1)),(2-p(2))cdots(N-p(N)) ímpar. Para qualquer bijeção , com , prove que
é sempre um número par.”
Conteúdo envolvido: teoria de números (par/ímpar), propriedades de diferença e produto, e o princípio da casa dos pombos (pigeonhole). Vamos usar que “um produto é par se e só se pelo menos um dos seus fatores for par” e também que “diferença de dois números de mesma paridade é par”.

Passo 2

Primeiro, lembra da definição de par e ímpar:
  • Um número é par se ele pode ser escrito como .
  • Um número é ímpar se pode ser escrito como .
    Propriedade chave:
    Se e são ambos pares ou ambos ímpares, então é par.
    Prova rápida:
  • Se e , então .
  • Se e , então .

Passo 3

Agora, conta quantos pares e quantos ímpares existem em , quando é ímpar.
Escrevendo , temos
  • Ímpares em : . São números.
  • Pares em : . São números.

Passo 4

Como é bijeção, ela manda os números ímpares do domínio em valores no contradomínio, que tem só pares disponíveis. Pelo princípio da casa dos pombos, pelo menos um desses ímpares do domínio só pode ir parar em um ímpar no contradomínio (pois não há pares suficientes). Ou seja, existe um índice ímpar tal que também é ímpar.

Passo 5

Para esse P(p) ;=;prodj=1^N l(j - p(j)r) ímpar, ambos e são ímpares, então é par (usando o que falamos no passo 2). Logo, o fator em
é par.

Resposta

Pelo fato de haver pelo menos um fator par no produto , concluímos que é um número par.

Exercícios relacionados