Um enxadrista, durante 11 semanas, joga pelo menos uma partida por dia mas não joga mais de 12 partidas por semana. Mostre que é possível achar um conjunto de dias consecutivos durante os quais ele jogou exatamente 20 partidas.

Passo 1

O enunciado considera um enxadrista que, ao longo de 11 semanas (ou seja, 77 dias), joga pelo menos uma partida por dia e no máximo 12 partidas por semana. Queremos mostrar que existe um segmento de dias consecutivos cuja soma de partidas é exatamente 20. O conteúdo-chave aqui é o princípio da casa-dos-pombos (pigeonhole principle) aplicado às somas cumulativas.

Passo 2

Denotemos por d_k o número de partidas jogadas no k-ésimo dia, para k=1,2,\dots,77. Como joga ao menos uma partida por dia, temos
d_k \ge 1
e, somando ao longo de uma semana de 7 dias, cada semana tem no máximo 12 partidas, o que implica ao final de 77 dias
\sum_{k=1}^{77} d_k \le 11 \times 12 = 132.
Definimos então as somas parciais
S_n = \sum_{k=1}^{n} d_k,
para n=1,2,\dots,77. Note que \{S_n\} é estritamente crescente e
1 \le S_1 < S_2 < \cdots < S_{77} \le 132.

Passo 3

Agora consideramos duas sequências de números:
\bigl\{S_1, S_2,\dots,S_{77}\bigr\} \quad\text{e}\quad \bigl\{S_1+20, S_2+20,\dots,S_{77}+20\bigr\}.
Na primeira, cada S_n está no intervalo de \;[1,132]. Na segunda, cada S_n+20 está em [21,152]. Logo, temos ao todo 77+77=154 números distribuídos entre 1 e 152, ou seja, apenas 152 “gavetas” possíveis. Pelo princípio da casa-dos-pombos, deve haver duas dessas 154 quantidades iguais.

Passo 4

Não pode ocorrer igualdade entre dois elementos da mesma sequência \{S_n\}, pois ela é estritamente crescente. Logo a colisão ocorre forçosamente entre um elemento de \{S_i\} e um de \{S_j+20\}. Assim, existem índices i e j tais que
S_i = S_j + 20.
Como S_n é crescente, fica necessariamente i>j. Dessa igualdade tiramos
S_i - S_j = 20
ou seja,
\sum_{k=j+1}^{i} d_k = 20.
Isso significa que o bloco de dias de j+1 até i foi jogado um total de 20 partidas.

Resposta

Concluímos que sempre existe um conjunto de dias consecutivos em que o enxadrista jogou exatamente 20 partidas.

Exercícios relacionados