If $a_i\geq 1\ \forall i\in\{1,...,120\}$ and $\sum_{i=1}^{120}a_i\leq 180$, there exist indices $i,j$ such that $\sum_{k=i}^ja_k=59$

Question

Let's consider 120 numbers $a_1,a_2,...,a_{120}\in \mathbb{N}$ such that $a_i\geq 1\ \forall i\in\{1,...,120\}$ and $\sum_{i=1}^{120}a_i\leq 180$. Prove that there exist indices $i, j$ such that $\sum_{k=i}^j a_k = 59$.

I think that I might be able to use the pigeonhole principle somehow, but I am not sure what would correspond to the pigeons here... The nests could possibly be 60 and the pigeons 59, solely by intuition, but I am not sure of anything else. Any help?

score 1 · Answer 1 · answered May 14 '18 at 19:51

1

You can indeed use the pigeonhole principle. Suppose the statement doesn't hold. If there are two sums divisible by 59, then these sum to 118 and 177, whose difference is 59, a contradiction. Then, there are 119 initial sums partitioned to 59 remainders modulo 59. Thus, three leave the same remainder, let's call them $a<b<c$. If $c-a\leq 118$, then we are done. Thus, it must be that $c-a=177$ and $b-a=118$. However, that gives $c-b=59$. We get a contradiction, and the proof is complete.

answered May 14 '18 at 19:51

George K

492

Why can we assume the existence of two sums divisible by 59? – GNUSupporter 8964民主女神地下教會 May 14 '18 at 19:55
We can't. It's just the easy case, so I do it first. The rest of the proof deals with the case where there are no two such sums. – George K May 14 '18 at 20:01
In the easy case, why must we have 118 and 177, instead of two sums of 118? – GNUSupporter 8964民主女神地下教會 May 14 '18 at 20:07
They are initial sums, and $a_i\geq 1$. They are never equal. – George K May 14 '18 at 20:08
By saying "initial sum", you mean a partial sum starting with the first term? (i.e $a_1 + \cdots + a_k$) – GNUSupporter 8964民主女神地下教會 May 14 '18 at 20:10
Yes, I mean exactly that. – George K May 14 '18 at 20:13
Thanks for explanation. Nice use of PHP! – GNUSupporter 8964民主女神地下教會 May 14 '18 at 20:20

If $a_i\geq 1\ \forall i\in\{1,...,120\}$ and $\sum_{i=1}^{120}a_i\leq 180$, there exist indices $i,j$ such that $\sum_{k=i}^ja_k=59$

1 Answers1