1

Al has 75 days to master discrete mathematics. He decides to study at least one hour every day, but no more than a total of 125 hours. Assume Al always studies in one hour units. Show there must be a sequence of consecutive days during which he studies exactly 24 hours.

omair azam
  • 115
  • I think I'm missing something... couldn't Al just study one hour a day for 75 days? – graydad Sep 25 '14 at 20:45
  • Well a starting point is at least one hour a day produces 75 hours (is this enough to learn discrete maths?) or two hours a day is over shooting by 25 hours. So the question is can you learn discrete maths in less than 125 hours? It seem under defined from that point? – Chinny84 Sep 25 '14 at 20:48
  • i dont know what it can imply....this is how i saw this question... some pigenhole concepts are applied somewhere... this is a bit complex to me.. – omair azam Sep 25 '14 at 20:51
  • The question as written doesn't make sense, since he can study 23 hours on the first day, 23 hours on the second day, 7 hours the third day, and one hour each other day. – David P Sep 25 '14 at 21:14

1 Answers1

0

Let $a_k$ be the number of hours of work Al has done after $k$ days. Then $\{a_1, a_2, a_3, \ldots, a_{75}\}$ is an increasing sequence of distinct positive integers since Al does at least one hour of work each day. Observe that $1 \leq a_k \leq 125$ since Al does at most $125$ hours of work over the $75$ days.

Let $b_k = a_k + 24$. Then the sequence $\{b_1, b_2, b_3, \ldots, b_{75}\}$ is also an increasing sequence of distinct positive integers. Observe that $1 + 24 = 25 \leq b_k \leq 149 = 125 + 24$.

Now consider the union of the two sequences. It consists of $150$ numbers that are at least $1$ and at most $149$. Thus, two of them must be the same. Hence, $b_k = a_k + 24 = a_j$ for some $j, k$. Thus, $a_j - a_k = 24$, so Al does exactly $24$ hours of work from day $a_{k + 1}$ to day $a_j$.

This is a clever application of the Pigeonhole Principle that forced me to consult my combinatorics notes.

N. F. Taussig
  • 76,571