Considere d como um número inteiro positivo. Mostre que entre um grupo de d+1 números inteiros (não necessariamente consecutivos) há dois com exatamente o mesmo resto quando divididos por d.

Passo 1

O enunciado pede para mostrar que, dado um inteiro positivo d e quaisquer d+1 números inteiros, sempre podemos encontrar dois deles que deixam o mesmo resto na divisão por d. O conteúdo principal aqui é o Princípio da Casa dos Pombos (pigeonhole principle).

Passo 2

Seja \{a_1,a_2,\dots,a_{d+1}\} o conjunto dos d+1 inteiros. Para cada a_k definimos o seu resto na divisão por d: existe único r_k\in\{0,1,\dots,d-1\} tal que
a_k \equiv r_k \pmod d.

Passo 3

Note que há exatamente d valores possíveis de resto: 0,1,\dots,d-1. Mas estamos atribuindo a estes d “caixas” de restos um total de d+1 números a_1,\dots,a_{d+1}.

Passo 4

Pelo Princípio da Casa dos Pombos, se temos mais “pombos” ( d+1 números) do que “caixas” ( d restos), então pelo menos duas vezes um mesmo resto deve ocorrer. Isto é, existem índices i\neq j tais que
r_i = r_j.
Logo
a_i \equiv r_i \equiv r_j \equiv a_j \pmod d,
ou seja, a_i e a_j deixam exatamente o mesmo resto na divisão por d.

Resposta

Entre quaisquer d+1 inteiros existem sempre dois que têm o mesmo resto na divisão por d.

Exercícios relacionados