Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
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.) –  Rex Kerr Dec 20 '11 at 15:10
    
I think you can do better, that there is at least one triple adding up to at least 33. :) –  Thomas Belulovich Dec 20 '11 at 21:54

2 Answers 2

up vote 11 down vote accepted

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?

share|improve this answer

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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