6

If the first 10 positive integer is placed around a circle, in any order, there exists 3 integer in consecutive locations around the circle that have a sum greater than or equal to 17?

This was from a textbook called "Discrete math and its application", however it does not provide solution for this question.

May I know how to tackle this question.

Edit: I relook at the actual question and realize it is sum greater or equal to 17. My apologies.

Jun Hao
  • 317
  • 1
    You accepted an answer that doesn't answer the question as posed. Did you mean $\ge17$? Since $\gt17$ is actually true (I checked by enumeration), the question as posed is valid and remains unanswered. – joriki Mar 03 '13 at 09:59
  • Even if OP changes to $\ge 17$ it still is interesting to find a nonenumerative proof of $>17$. – coffeemath Mar 03 '13 at 10:30
  • Yes. I relize my question posted was wrong. My apologies.

    Yet at the same time, it will be very interesting to see a proof for > 17.

     – Jun Hao Mar 03 '13 at 14:24
  • 2
    The "wrong" question led to better answers than the "right" question would have. No need to apologize. – Gerry Myerson Mar 03 '13 at 22:44
  • $18$ is possible, for example with $1,7,3,8,4,5,9,2,6,10$ and many others – Henry Sep 14 '18 at 11:21

5 Answers5

9

Gerry's answer shows that the average sum of the triples is $16.5$. If there's no sum above $17$, then at least five sums have to be $17$ for the average to be $16.5$. Since two successive sums can't be equal, at most five sums are $17$, and thus exactly five sums are $17$, and thus the other five sums are $16$ and they alternate. But that's impossible, because it implies that moving by three goes up or down by $1$ and moving another three goes down or up by $1$, respectively, leading to the same number again.

joriki
  • 238,052
7

Remove the number 1 and unwrap the circle of numbers into a row $a, b, c, d, e, f, g, h, i$, where $\{a, b, c, d, e, f, g, h, i\}=\{2,3,4,5,6,7,8,9,10\}$. Then $(a+b+c)+(d+e+f)+(g+h+i)=\sum_{j=2}^{10}j = 54$, therefore at least one of $(a+b+c), (d+e+f),$ or $(g+h+i)$ must be $\ge {54\over3}=18$.

Steve Kass
  • 14,881
4

EDIT: it has been pointed out that this answer only gives $\ge17$, while the question asks for $\gt17$. More work is needed.

Let $A_1=a_1+a_2+a_3$, $A_2=a_2+a_3+a_4$, and so on, $A_{10}=a_{10}+a_1+a_2$. Then $A_1+A_2+\cdots+A_{10}=3(a_1+a_2+\cdots+a_{10})=(3)(55)=165$, so some $A_i\ge165/10=16.5$, so some $A_i\ge17$.

Gerry Myerson
  • 179,216
  • I think the question is $> 17$, not $\geq 17$. (My solution was that a random triple has sum 16.5, so there must be one such that $\geq 17$, but it does not work for $> 17$.) – dtldarek Mar 03 '13 at 08:37
  • 1
    Perhaps the inequality ( > 17) is true for more complicated reasons. Can anybody find an example with every triple $\le$ 17? – TonyK Mar 03 '13 at 09:29
  • 1
    @Tony: I checked by enumeration; the minimal maximal sum is indeed $18$, for 1 4 9 5 3 7 8 2 6 10. – joriki Mar 03 '13 at 09:57
  • 1
    So now all we need is a proof... – TonyK Mar 03 '13 at 10:00
  • @Gerry: I found a relatively simple proof for $\gt17$ that builds on your proof for $\ge17$. – joriki Mar 03 '13 at 12:33
1

Original answer:

To have all sums $\le17$, all four numbers from $7$ to $10$ would have to be separated by at least two numbers; but it would take at least $12$ slots to space them like that.

As has been pointed out in the comments, this is wrong, but Gerry showed how to complete it.

The numbers from $8$ to $10$ must be separated by at least two numbers. That leaves two number to separate the $7$ from them. If it's not adjacent to any of them, it must be separated from both $8$ and $9$ by just one number, and those have to be $2$ and $1$, respectively; that leaves only $3$ to $6$ in the four slots around $10$, which leads to at least one sum of at least $18$.

So the $7$ must be next to one of the numbers from $8$ to $10$. It can't be next to the $9$ or $10$ because that would lead to a sum of at least $18$ even with $1$ and $2$ adjacent. So it must be next to the $8$, and Gerry's argument completes the proof.

That's rather inelegant case work; a more systematic proof would be nice.

joriki
  • 238,052
  • 1
    Couldn't $7$ be adjacent to $8$ without causing problems? – EuYu Mar 03 '13 at 11:10
  • 7+8 is only 15, leaving a possibility of inserting either a single 1 or a single 2 between them. Maybe one needs to consider the possible cyclic patterns among 7,8,9,10. [Even between 7 and 9 there could be a single 1.] – coffeemath Mar 03 '13 at 11:14
  • 1
    If 7 and 8 are adjacent, we must have 1-7-8-2 (or 2-7-8-1). Then a-b-10-c-d must have a triple too big, e.g., a-b-10-c-1-7-8-2 and even if a, b, c is some arrangement of 3, 4, 5 there will be a sum 18 or more. – Gerry Myerson Mar 03 '13 at 11:19
-1

Solution: For any given the first 10 positive integers placed around a circle, in any order, there are exactly 10 choices of 3 consecutive numbers around the circle. And each number appears exactly 3 times among the 10 choices. Hence, the sum of all numbers in 10 choices of 3 adjacent number is (1 + 2 + · · · + 10) × 3 = 165 This implies that at least one choice of 3 adjacent numbers has a sum greater than or equal to 17. Indeed, if there is no such triple, the sum of all numbers in 10 triples will be strictly less than 160 because each one is strictly less than 16. This contradicts to the sum of all triples is 165.

Brandon
  • 1