Here's a question we got for homework:

We write down all the numbers from $1$ to $20$ in a circle. Prove that there is a sequence of $3$ numbers whose sum is at least $32$.

I assume we need the pigeonhole principle as we had a similar example in class where they used the modulo relation to divide the numbers into different sets. I fail to see how that would help me in this case. I thought about starting with counting the number of solutions to the equation $k_1+\cdots+k_{20} = 32$, but then I'd have to do the same for $33, 35$ and so on. Doesn't seem very smart.

Any ideas? Thanks!

  • 1
    $\begingroup$ That's not very good phrasing for the question--the trivial solution is "18+19+20>32". It should have been something like, Suppose that numbers from 1 to 20 are written down in a circle in random order. Prove that regardless of order there will be a sequence of 3 numbers whose sum is at least 32. (I'd probably actually use the idea of permutation, but as homework I'm unsure whether that'd be intimately familiar at this point in the class.) $\endgroup$ – Rex Kerr Dec 20 '11 at 15:10
  • $\begingroup$ I think you can do better, that there is at least one triple adding up to at least 33. :) $\endgroup$ – Thomas Belulovich Dec 20 '11 at 21:54
  • $\begingroup$ Please do not use the word "number" as a synonym for "integer" or "natural number". $\endgroup$ – DanielV Feb 24 '15 at 1:17

Suppose that the sums of sequences of three adjacent numbers in the circle are $s_1,s_2,\dots,s_{20}$. When you form the grand sum $s_1+s_2+\cdots+s_{20}$, in effect you’re adding up the numbers from $1$ through $20$ three times (why?), so you know the total. If all of the $s_k$ were less than $32$, what would the maximum possible total be?


We can in fact prove that there is always three successive integers in this arrangement, whose sum is at least $33$. Though it is not clear if $33$ is the optimal lower bound.

Consider the circular arrangement of numbers starting from $1$ as follows. $$1 , a_1, a_2, \ldots, a_{19}$$ where $a_1,a_2,\ldots a_{19} \in \{2,3,4,\ldots,20\}$.

Note that $1 + a_1 + a_2 + \cdots a_{19} = 210$. Note that at least one of $a_1,a_4,a_7,a_{10},a_{13},a_{16},a_{19}$ must be $\leq 14$.

Say $a_1 \leq 14$, then we get that $1 + a_1 + a_2 + \cdots a_{19} \leq 1 + 14 + a_2 + \cdots a_{19}$. Let $s$ be the maximum possible sum of three consecutive elements. Then we have that $$(a_2 + a_3 + a_4) + (a_5 + a_6 + a_7) + \cdots +(a_{17} + a_{18} + a_{19}) \leq 6s$$

Hence, we get that $$210 = 1 + a_1 + a_2 + \cdots a_{19} \leq 1 + 14 + a_2 + \cdots a_{19} \leq 6s + 15$$ i.e. $$6s \geq 195 \implies s \geq 32.5.$$ Hence, $$s \geq 33.$$

The same argument works if $a_1 > 14$ and one of $a_4,a_7,a_{10},a_{13},a_{16},a_{19} \leq 14$. For instance, if $a_7 \leq 14$, then rearrange the sum as $$1 + (a_1 + a_2 + a_3) + (a_4 + a_5 + a_6) + a_7 + (a_8 + a_9 + a_{10}) + (a_{11} + a_{12} + a_{13}) + (a_{14} + a_{15} + a_{16}) + (a_{17} + a_{18} + a_{19}).$$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.