- Dados 1000 inteiros, prove que existem dois deles cuja soma ou subtração é um múltiplo de 1997.
- Sejam
inteiros positivos nào excedendo 125. Prove que entre 43 diferenças consecutivas
, algum valor deve ocorrer ao menos 10 vezes.
Passo 1
(Questão
) Temos
números inteiros quaisquer e queremos mostrar que entre eles existem dois cuja soma ou cuja diferença é múltiplo de
. O conteúdo é o Princípio da Casa dos Pombos aplicado a classes de resíduos módulo
.
Passo 2
Agrupamos as
classes de resíduos módulo
em
“caixas” assim:
— Uma caixa para a classe ;\n
— Para cada , juntamos as classes
e
numa única caixa.
— Uma caixa para a classe
— Para cada
Dessa forma há
caixas, e cada número cai exatamente em uma delas conforme seu resíduo.
Passo 3
Pelo Princípio da Casa dos Pombos, ao colocarmos
números em
caixas, alguma caixa recebe pelo menos dois números.
- Se for a caixa da classe
, temos dois números , logo
- Se for uma caixa que junta
e , e os dois números têm o mesmo resíduo , então
Se eles tiverem resíduos distintos
e
, então
Passo 4
(Questão
) Temos
inteiros positivos não excedendo
. Definimos as diferenças
Então cada
é inteiro positivo e
Queremos provar que algum valor aparece pelo menos
vezes nessa lista de
diferenças.
Passo 5
Suponha, por contradição, que cada valor possível ocorra no máximo
vezes. Para preencher
posições com essa restrição, precisamos de pelo menos
valores distintos. Para minimizar a soma
usando exatamente
valores positivos distintos, escolhemos os cinco menores:
. Distribuímos
cópias de cada um dos quatro menores (
) e as restantes
cópias de
. Então a soma mínima possível seria
Passo 6
Isso entra em contradição com
Logo a hipótese de “cada valor aparece no máximo
vezes” falha.
Resposta
Entre as
diferenças
, existe necessariamente algum valor que ocorre pelo menos
vezes.