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:
  • 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:
  1. Escrever cada número como .
  2. Olhar só a parte “par” ou “ímpar” desses expoentes, ou seja, .
  3. Aplicar pigeonhole: 9 números em 8 combinações de paridades garantem pelo menos duas iguais.
  4. 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 .

Passo 3

Como cada número não tem primos maiores que 5, ele se escreve assim:
N = 2^a ;3^b;5^c,
onde são inteiros não-negativos.

Passo 4

Repara só se o expoente é par ou ímpar. Definimos o vetor de paridades
l(abmod2,;bbmod2,;cbmod2r),
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 (aibmod2,bibmod2,cibmod2) =,(ajbmod2,bjbmod2,cjbmod2) e , caem na mesma casa, ou seja,

Passo 6

Olha o produto desses dois:
Ni,Nj =2^ai+aj;3^bi+bj;5^ci+cj
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.

Exercícios relacionados