Pigeonhole Principle question - sum of positive integers

148 Views Asked by At

A question that should be solved with pigeonhole but I'm having problems.

$a_1,a_2,a_3,...,a_{77}$ are positive integers.

We are given that $a_1+a_2+a_3+...+a_{76}+a_{77} < 133$

Show that there are numbers $k,l \in \{1,2,3,...,77\}$ such that $ k<l$ and:

$a_k+a_{k+1}+a_{k+2}+...+a_{l-1}+a_l = 21$

1

There are 1 best solutions below

0
On BEST ANSWER

Let $s_k = a_{11k+1} + \cdots + a_{11k+22}$, for $0\leq k \leq 5$. Then $s_0 + \cdots + s_5 + a_1 + \cdots + a_{11} + a_{67} + \cdots + a_{77} = 2(a_1 + \cdots + a_{77}) \leq 264$. Since each $a_i \geq 1$, this means $s_1 + \cdots + s_5 \leq 242 < 6\cdot 41$. Hence for some $k$, $0\leq k \leq 5$, $s_k < 41$.

For such a $k$, consider the sums $r_m = a_{11k+1} + \cdots + a_{11k+m}$, where $0\leq m\leq 21$ ($r_0=0$). Now use pigeonhole to show that some $r_p$ and $r_q$ (with $q>p$) are congruent modulo $21$. Use the size bound on $s_k$ to show that (a) the difference must be exactly 21, and (b) for such a pair $p, q$, we must have $q>p+1$, so that $r_q-r_p$ is the sum we seek.