6
$\begingroup$

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
    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.)2011-12-20
  • 0
    I think you can do better, that there is at least one triple adding up to at least 33. :)2011-12-20
  • 0
    Please do not use the word "number" as a synonym for "integer" or "natural number".2015-02-24

2 Answers 2

14

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?

2

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}).$$