Mostrar que entre nove números que não possuem divisores primos maiores que cinco, existem dois cujo produto é um quadrado perfeito.
Passo 1
Beleza, você tem nove números, cada um só pode ter 2, 3 ou 5 na fatoração (ou seja, não há primos maiores que 5). O que a gente quer provar é que, entre esses nove, sempre dá pra achar dois cujo produto é um quadrado perfeito.
Conteúdo que vamos usar:
Conteúdo que vamos usar:
- Fatoração única (teorema fundamental da aritmética)
- Definição de quadrado perfeito (todos os expoentes na fatoração são pares)
- Princípio da Casa dos Pombos (pigeonhole principle)
O que precisamos fazer:
- Escrever cada número como
. - Olhar só a parte “par” ou “ímpar” desses expoentes, ou seja,
. - Aplicar pigeonhole: 9 números em 8 combinações de paridades garantem pelo menos duas iguais.
- Mostrar que esses dois com mesma paridade formam um produto cuja todos os expoentes somados são pares, logo é quadrado perfeito.
Passo 2
Primeiro, o que é um quadrado perfeito?
Um número é quadrado perfeito se, ao fatorar, todos os expoentes são pares. Por exemplo, : os expoentes 2 e 2 são pares. Isso acontece porque
.
Um número é quadrado perfeito se, ao fatorar, todos os expoentes são pares. Por exemplo,
Passo 3
Como cada número não tem primos maiores que 5, ele se escreve assim:
onde
são inteiros não-negativos.
Passo 4
Repara só se o expoente é par ou ímpar. Definimos o vetor de paridades
que só pode ser cada coordenada 0 (par) ou 1 (ímpar). Então há
vetores possíveis.
Passo 5
Agora vem o Princípio da Casa dos Pombos: temos 9 números (pombos) e só 8 vetores de paridades (casas). Logo, dois desses números, digamos
e
, caem na mesma casa, ou seja,
Passo 6
Olha o produto desses dois:
Como
, a soma
é par. Mesma coisa para
e
. Logo todos os expoentes do produto são pares, o que diz exatamente que
é um quadrado perfeito.
Resposta
Entre quaisquer nove números sem primos maiores que 5 sempre existem dois cujo produto é um quadrado perfeito.