I set out to solve the following question using the pigeonhole principle

Regardless of how one arranges numbers $1$ to $10$ in a circle, there will always exist a pair of three adjacent numbers in the circle that sum up to $17$ or more.

My outline

[1] There are $10$ triplets consisting of adjacent numbers in the circle, and since each number appears thrice, the total sum of these adjacent triplets for all permutations of the number in the circle, is $3\cdot 55=165$.

[2] If we consider that all the adjacent triplets sum to 16 , and since there are $10$ such triplets, the sum accordingly would be $160$, but we just said the invariant sum is $165$ hence there would have to be a triplet with sum of $17$ or more.

My query

Could someone polish this into a mathematical proof and also clarify if I did make use of the pigeonhole principle.

  • $\begingroup$ Yes, you used pigeonhole. Should say if all sums are $\le 16$, then the sum is $\le 160$. $\endgroup$ – André Nicolas May 25 '13 at 4:42
  • $\begingroup$ @AndréNicolas noted and aha , the syntax part is exactly why I asked the question on here. $\endgroup$ – metric-space May 25 '13 at 4:44
  • $\begingroup$ @nerorevenge Note: You can actually show that the 3 adjacent numbers sum to 18 or more. $\endgroup$ – Calvin Lin May 25 '13 at 8:37

Yes, you used the Pigeonhole Principle. As a very mild correction, you should say that of all sums of three consecutives are $\le 16$, then the sum is $\le 160$.

The proof (with the small correction) is already fully mathematical. Conceivably you might want to explain the $55$ further. It is clear to you and to most users of this site why $55$, but imagine the reader to be easily puzzled.

The part about "all the permutations" is vague, and technically incorrect. You are finding the sum of a consecutive triple, and summing all these sums. Permutations have nothing to do with it, we are talking about a particular fixed arrangement of the numbers.

Remark: We could use a lot of symbols. Starting at a particular place, and going counterclockwise, let our numbers be $a_1,a_2,\dots,a_{10}$. For any $i$, where $1\le i\le 10$, let $S_i=a_i+a_{i+1}+a_{i+2}$, where we use the convention that $a_{10+1}=a_1$, $a_{10+2}=a_2$, and $a_{9+2}=a_1$.

Then $S_1+S_1+\cdots+S_{10}=165$, since each of $1$ to $10$ appears in $3$ of the $S_i$, and $1+2+\cdots+10=55$.

But if all the $S_i$ are $\le 16$, then $\sum_{i=1}^{10}S_i\le 160$. This contradicts the fact that $\sum_{i=1}^{10}S_i=165$.

I prefer your proof, mildly modified.

| cite | improve this answer | |
  • $\begingroup$ eh, is that all? the reason I'm asking is that, inb the past my so called 'proofs' have been criticised for being too informal $\endgroup$ – metric-space May 25 '13 at 4:45
  • $\begingroup$ @nerorevenge: I am an advocate of the informal but clear. I hope that someone more formal-minded will add an answer. The only issue is that you perhaps left an easily filled gap or two. $\endgroup$ – André Nicolas May 25 '13 at 4:53
  • $\begingroup$ I have added another criticism. You should really fix the wording there. $\endgroup$ – André Nicolas May 25 '13 at 4:58
  • $\begingroup$ I agree.That definitely is vaguely worded. $\endgroup$ – metric-space May 25 '13 at 4:59
  • $\begingroup$ Presumably the "pair" wording came with the problem. But it looks funny to call a trio a pair. $\endgroup$ – André Nicolas May 25 '13 at 5:23

We will show something stronger, namely that there exists 3 adjacent numbers that sum to 18 or more.

Let the integers be $\{a_i\}_{i=1}^{10}$. WLOG, $a_1 = 1$. Consider

$$a_2 + a_3 + a_4, a_5 + a_6 + a_7, a_8 + a_9 + a_{10}$$

The sum of these 3 numbers is $2+3 +\ldots + 10 = 54$. Hence, by the pigeonhole principle, there exists one number which is at least $\lfloor \frac{54}{3} \rfloor = 18 $.

I leave it to you to show that there is a construction where no 3 adjacent numbers sum to 19 or more, which shows that 18 is the best that we can do.

| cite | improve this answer | |
  • $\begingroup$ definitely a stronger proof ,and I have admit it sure is nice, I wonder why cut-the-knot.org didn't ask people to solve for what you proved. $\endgroup$ – metric-space May 25 '13 at 16:45
  • 1
    $\begingroup$ @nerorevenge I used this as a problem on Brilliant.org, and most could only get to 17, and didn't understand why 18 must be true. The 18 case arises quite easily by ignoring the small values which would otherwise reduce our sum. $\endgroup$ – Calvin Lin May 25 '13 at 23:37

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.