Seja
ímpar. Provar que para qualquer bijeção
do conjunto
, o produto
é necessariamente par.
Dica: O produto de vários fatores é par se, e somente se, um dos fatores é 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
í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”.
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:
See 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
Escrevendo
- Í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
í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.