É dado um conjunto A=\left\{a_{1}, \ldots, a_{m}\right\} de m números inteiros ( m>1 ). Mostre que existem inteiros r, s satisfazendo 1 \leq r \leq s \leq m, tais que
a_{r}+a_{r+1}+\cdots+a_{s}
é múltiplo de m.

Passo 1

O enunciado dá um conjunto A=\{a_{1},\dots,a_{m}\} de m inteiros com m>1 e pede para mostrar que existem índices r,s com 1\le r\le s\le m tais que
a_{r}+a_{r+1}+\cdots+a_{s}
é múltiplo de m. O conteúdo principal aqui é o Princípio da Casa dos Pombos aplicado a somas parciais e resíduos módulo m.

Passo 2

Definimos as somas parciais
S_{k} = a_{1} + a_{2} + \cdots + a_{k},
para cada k=1,2,\dots,m. Vamos olhar cada S_{k} módulo m, ou seja, o resíduo de S_{k} em \{0,1,2,\dots,m-1\}.

Passo 3

Se algum S_{k} for congruente a zero módulo m, ou seja,
S_{k}\equiv 0\pmod{m},
então a soma dos primeiros k termos é múltiplo de m. Basta escolher
r=1,\quad s=k
e estamos prontos.

Passo 4

Caso nenhum S_{k} seja \equiv 0\pmod{m}, então cada S_{k} ocupa um dos m-1 resíduos não nulos \{1,2,\dots,m-1\}. Mas temos m valores S_{1},S_{2},\dots,S_{m} e só m-1 recipientes de resíduos, logo por Pigeonhole existem i<j tais que
S_{i}\equiv S_{j}\pmod{m}.

Passo 5

Se S_{i}\equiv S_{j}\pmod{m} com i<j, então
S_{j}-S_{i} = (a_{1}+\cdots+a_{j}) - (a_{1}+\cdots+a_{i}) = a_{i+1} + \cdots + a_{j}
é múltiplo de m. Basta escolher
r = i+1,\quad s = j
e encontramos o bloco de termos cuja soma é divisível por m.

Resposta

Mostramos que em todo caso existe um par (r,s), 1\le r\le s\le m, tal que
a_{r}+a_{r+1}+\cdots+a_{s}
é múltiplo de m.

Exercícios relacionados