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:
  • 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
sk = número de livros vendidos do dia 1 até o dia kúé
Também definimos s0 = 0 (nenhum dia, nenhuma venda). Como ele vende ao menos 1 livro por dia, cada dia adiciona algo, então
s0 < s1 < s2 < cdots < s305 = 463
Ou seja, esses 306 valores ( s0, s1, dots, s305) são todos distintos e vão de 0 até 463.

Passo 3

Agora, a ideia esperta: considere também os valores
sk + 144, k = 0,1,2,dots,305
Isso forma outro conjunto de 306 números que vai de 144 até 463 + 144 = 607.
Então temos, no total, 612 números:
A = s0, s1, dots, s305,
B = s0 + 144, s1 + 144, dots, s305 + 144.
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 sk crescem sempre) e dentro de B também não (os sk+144 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 i e j tais que
si = sj + 144
Como sk é crescente, i>j.

Passo 5

Esse i>j significa que entre o dia j+1 e o dia i ele vendeu
si - sj = 144
livros. Pronto, achamos um período de dias consecutivos com exatamente 144 vendas.

Resposta

Existe, sim, um intervalo de dias consecutivos (do dia j+1 ao dia i) em que o livreiro vendeu exatamente 144 livros.

Exercícios relacionados