Quantos pares ordenados de números inteiros (a, b) são necessários para garantir que haja dois pares ordenados ( a_{1}, \left.b_{1}\right) e \left(a_{2}, b_{2}\right), tal que a_{1} \bmod 5=a_{2} \bmod 5 e b_{1} \bmod 5=b_{2} mod 5?

Passo 1

O enunciado pergunta quantos pares ordenados de inteiros (a,b) precisamos escolher para garantir que existam dois pares (a_{1},b_{1}) e (a_{2},b_{2}) tais que
a_{1}\bmod 5 = a_{2}\bmod 5 \quad\text{e}\quad b_{1}\bmod 5 = b_{2}\bmod 5.
O conteúdo principal é o Princípio da Casa dos Pombos (pigeonhole principle).

Passo 2

Cada par (a,b) pode ser classificado pelo par de resíduos \bigl(a\bmod 5,\;b\bmod 5\bigr). Como a\bmod 5 tem \,5 possibilidades e b\bmod 5 também tem \,5, o total de classes de equivalência é
5 \times 5 = 25.

Passo 3

Pelo Princípio da Casa dos Pombos, para garantir que em alguma dessas 25 classes haja pelo menos dois pares distintos, precisamos de
25 + 1 = 26
pares ordenados. Assim, ao escolhermos \,26 pares, obrigatoriamente dois deles cairão na mesma classe de resíduos.

Resposta

26

Exercícios relacionados