An arm wrestler is the champion for a period of 75 hours…

combinatoricsdiscrete mathematicspigeonhole-principle

An arm wrestler is the champion for a period of 75 hours. (Here, by
an hour, we mean a period starting from an exact hour, such as
1p.m., until the next hour.)

The arm wrestler had at least one match
an hour, but no more than 125 total matches. Show that there is a
period of consecutive hours during which the arm wrestler had exactly
24 matches.

I am completely baffled by this problem. What does this problem actually mean??
I have tried my level best to understand it but no luck.

Best Answer

Let $m_i$ be the number of matches fought in hour $j$, so we have $m_i \ge 1$ for $1 \le i \le 75$. Define $$s_n = \sum_{i=1}^n m_i$$ for $1 \le n \le 75$. If we consider the values $s_n$ modulo $24$, there are $24$ possible slots and $75$ numbers, so there must be some slot that contains at least $4$ numbers, by the pigeonhole principle. Let's say the $4$ numbers are $s_a, s_b, s_c$ and $s_d$, with $a<b<c<d$, so $s_a=s_b=s_c=s_d \pmod{24}$. Then $s_b-s_a = s_c-s_b=s_d-s_c = 0 \pmod{24}$, so $$\sum_{i=a+1}^b m_i = \sum_{i=b+1}^c m_i= \sum_{c+1}^d m_i = 0 \pmod{24} \tag{*}$$ Therefore each one of the three sums above must be one of the values $0, 24, 48, 72 \dots$ etc.

Zero is ruled out as a sum because we know $m_i \ge 1$ for all $i$. Can all three sums be $48$ or greater? No, because then the total of the three sums would be at least $144$, and we know the total number of matches was no more than $125$. So at least one of the sums listed in $(*)$ is equal to $24$, i.e. exactly $24$ matches were fought in one of the intervals $a+1$ to $b$, $b+1$ to $c$, or $c+1$ to $d$.

Related Question