Um certo livreiro vende pelo menos um livro por dia. Sabendo que o livreiro vendeu 463 livros durante 305 dias consecutivos, mostrar que em algum período de dias consecutivos o livreiro vendeu exatamente 144 livros.
Passo 1
Então, cara, o enunciado diz o seguinte: um livreiro vende pelo menos 1 livro por dia, durante 305 dias seguidos, e, no total, vendeu 463 livros. A gente precisa mostrar que existe um trecho de dias consecutivos em que ele vendeu exatamente 144 livros.
Conteúdo que vamos usar:
Conteúdo que vamos usar:
- Soma acumulada (prefix sums) pra traduzir “vendeu x livros até o dia n”.
- Princípio da gaveta (ou pigeonhole principle) pra garantir que dois desses valores batem com uma diferença de 144.
Passo 2
Primeiro, vamos definir a soma acumulada. Seja
Também definimos
Ou seja, esses 306 valores (
) são todos distintos e vão de 0 até 463.
Passo 3
Agora, a ideia esperta: considere também os valores
Isso forma outro conjunto de 306 números que vai de
Então temos, no total, 612 números:
A = ,
B = .
A =
B =
Esses 612 números estão dentro do intervalo de 0 até 607, que tem só 608 valores possíveis. Pelo princípio da gaveta, pelo menos dois desses 612 números precisam ser iguais.
Passo 4
Agora, detalhe importante: dentro de A não pode haver repetições (os
crescem sempre) e dentro de B também não (os
também crescem). Logo, a repetição tem que ser um número de A igual a um número de B. Ou seja, existem índices
e
tais que
Como
Passo 5
Esse
significa que entre o dia
e o dia
ele vendeu
livros. Pronto, achamos um período de dias consecutivos com exatamente 144 vendas.
Resposta
Existe, sim, um intervalo de dias consecutivos (do dia
ao dia
) em que o livreiro vendeu exatamente 144 livros.