4
$\begingroup$

A website was hit $300$ times over a $15$ day period. I must show that it was hit at least $60$ times over some period of $3$ consecutive days.

I was thinking that it would be best to solve this problem by contradiction and set up three day sections with $59$ total hits, but couldn't get anywhere with this method.

Can anyone help me with this?

Thanks!

2 Answers 2

8

Problems like this can be handled by the Pigeonhole Principle. This is one of my favorite tools in mathematics because of its usefulness and its intuitiveness. The Pigeonhole Principle states that if you have $m$ pigeons and $n$ boxes (or holes), and you place each pigeon in some box, then at least one box has at least $m/n$ pigeons inside it. This can also be worded as follows:

Suppose that you have $n$ real numbers $x_1, \dots , x_n$. Then

$$ x_1 + \dots + x_n = C \Longrightarrow x_i \geq \frac{C}{n} \quad \text{for some } i. $$

Similarly, if one has $n$ positive real numbers $x_1, \dots , x_n$, then

$$ x_1 \cdot \dots \cdot x_n = C \Longrightarrow x_1 \geq \sqrt[n]{C} \quad \text{for some } i. $$

The easiest proof of this is probably the proof of the contrapositive:

  • If one is given $n$ integers $x_1 , \dots , x_n$, and each of them is less than $\frac{C}{n}$, then

$$ x_1 + \dots + x_n < C. $$

  • 0
    +1 I always assumed that the pigeonhole principle was just for the 2-pigeons 1-hole case, i.e. when there are $m$ pigeons and $n$ holes, and $m > n$. I now know the general case!2011-04-26
  • 1
    @Michael If $m \leq n$, then this is true but not helpful. For example, if there are $4$ pigeons and $10$ holes, we only know there is at least one hole with $0.4$ pigeons in it! That sounded way more gruesome than I intended, since we are obviously not splitting pigeons!! (:2011-04-26
  • 0
    ah, sorry, I was not clear enough. I had only used the pidgeonhole principle to show that two pigeons must be in one hole, not that there must me at least $m/n$ pigeons in one hole.2011-04-26
  • 0
    @Michael. Gotcha. I understand now (:2011-04-26
5

Hint:

If the hits are $d_1, d_2, \dots, d_{15}$

and $y_1 = d_1 + d_2 + d_3$, $y_2 = d_4 + d_5 + d_6$, ..., $y_5 = d_{13}+d_{14} + d_{15}$.

Can you figure out something about the $y_i$?

  • 0
    I'm happy to delete my answer if you feel it's close to yours.2011-04-25
  • 0
    @DJC: No, please don't delete. Your answer is well written (+1 in fact).2011-04-25