0
$\begingroup$

A salesman sells at least $1$ car each day for $100$ consecutive days selling a total of $150$ cars. Prove that for each value of $n$, $1\le n \lt 50$, there is a period of consecutive days during which he sold a total of exactly $n$ cars.

How do you prove this through Pigeonhole? Thanks in advance.

$\endgroup$
  • $\begingroup$ What have you tried? $\endgroup$ – Calvin Lin Oct 2 '19 at 3:43
1
$\begingroup$

Let $T_k$ be the total number of cars sold from days 1 to $k$.

The goal is to show that $ \{ T_k \} \cap \{ T_k + n \}$ is non-empty.
There are a total of 200 values here. These are our balls.
The range of values is from 1 to $150+n < 200$. These are our holes. Hence, by PP, there is at one hole with at least 2 balls.

Can the 2 balls both come from $\{T_k\}$? (Explain why the answer is no.)
Can the 2 balls both come from $\{T_k + n\}$? (Explain why the answer is no.)
Hence, these 2 balls give us $T_i = T_j + n$.
So, from days $j+1$ to $i$, he sold $n$ cars.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.