1. Dados 1000 inteiros, prove que existem dois deles cuja soma ou subtração é um múltiplo de 1997.
  2. Sejam a_{1}<a_{2}<\ldots<a_{44} inteiros positivos nào excedendo 125. Prove que entre 43 diferenças consecutivas d_{i}= a_{i}+1-a_{i}, algum valor deve ocorrer ao menos 10 vezes.

Passo 1

(Questão 35) Temos 1000 números inteiros quaisquer e queremos mostrar que entre eles existem dois cuja soma ou cuja diferença é múltiplo de 1997. O conteúdo é o Princípio da Casa dos Pombos aplicado a classes de resíduos módulo 1997.

Passo 2

Agrupamos as 1997 classes de resíduos módulo 1997 em 999 “caixas” assim:
— Uma caixa para a classe 0;\n
— Para cada r\in\{1,2,\dots,998\}, juntamos as classes r e 1997-r numa única caixa.
Dessa forma há 1+998=999 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 1000 números em 999 caixas, alguma caixa recebe pelo menos dois números.
  • Se for a caixa da classe 0, temos dois números x,y\equiv0\pmod{1997}, logo
x-y\equiv0\pmod{1997}.
  • Se for uma caixa que junta r e 1997-r, e os dois números têm o mesmo resíduo r, então
x-y\equiv0\pmod{1997}.
Se eles tiverem resíduos distintos r e 1997-r, então
x+y\equiv r+(1997-r)\equiv0\pmod{1997}.

Passo 4

(Questão 36) Temos a_{1}<a_{2}<\cdots<a_{44} inteiros positivos não excedendo 125. Definimos as diferenças
d_{i}=a_{i+1}-a_{i},\quad i=1,2,\dots,43.
Então cada d_{i} é inteiro positivo e
\sum_{i=1}^{43}d_{i}=a_{44}-a_{1}\le125-1=124.
Queremos provar que algum valor aparece pelo menos 10 vezes nessa lista de 43 diferenças.

Passo 5

Suponha, por contradição, que cada valor possível ocorra no máximo 9 vezes. Para preencher 43 posições com essa restrição, precisamos de pelo menos
\bigl\lceil\tfrac{43}{9}\bigr\rceil=5
valores distintos. Para minimizar a soma \sum d_{i} usando exatamente 5 valores positivos distintos, escolhemos os cinco menores: 1,2,3,4,5. Distribuímos 9 cópias de cada um dos quatro menores ( 1,2,3,4) e as restantes 43-9\cdot4=7 cópias de 5. Então a soma mínima possível seria
9(1+2+3+4)+7\cdot5 =9\cdot10+35 =125.

Passo 6

Isso entra em contradição com
\sum_{i=1}^{43}d_{i}\le124.
Logo a hipótese de “cada valor aparece no máximo 9 vezes” falha.

Resposta

Entre as 43 diferenças d_{i}, existe necessariamente algum valor que ocorre pelo menos 10 vezes.

Exercícios de Livros Relacionados