É dado um conjunto
de
números inteiros (
). Mostre que existem inteiros
,
satisfazendo
, tais que
é múltiplo de
.
Passo 1
O enunciado dá um conjunto
de
inteiros com
e pede para mostrar que existem índices
com
tais que
é múltiplo de
. O conteúdo principal aqui é o Princípio da Casa dos Pombos aplicado a somas parciais e resíduos módulo
.
Passo 2
Definimos as somas parciais
para cada
. Vamos olhar cada
módulo
, ou seja, o resíduo de
em
.
Passo 3
Se algum
for congruente a zero módulo
, ou seja,
então a soma dos primeiros
termos é múltiplo de
. Basta escolher
e estamos prontos.
Passo 4
Caso nenhum
seja
, então cada
ocupa um dos
resíduos não nulos
. Mas temos
valores
e só
recipientes de resíduos, logo por Pigeonhole existem
tais que
Passo 5
Se
com
, então
é múltiplo de
. Basta escolher
e encontramos o bloco de termos cuja soma é divisível por
.
Resposta
Mostramos que em todo caso existe um par
,
, tal que
é múltiplo de
.