Find maximum value of number a such that for any arrangement of numbers 1,2,…,10 on a circle, we can find three consecutive numbers such their sum bigger or equal than a.
Problem
Source: Bosnia and Herzegovina 2011
Tags: combinatorics proposed, combinatorics
17.05.2011 15:02
We will prove that the maximum value of a is larger than or equal to 18. First, define x1,x2,⋯,x10 to be the numbers on the circle consecutively, x11=x1, x12=x2, and yk=xk+xk+1+xk+2 for 1≤k≤10. Note that since ∑xi=55, ∑yi=165, so that there exists some yi such that yi≥17. Then a≥17. Let us assume the contrary; that is, a≤17. So since a≥17, a must be equal to 17, so all yi must be less than or equal to 17. Note that yi and yi+1 can't be equal for any 1≤i≤10 (assume y11=y1), because if they are equal, then xi and xi+3 are equal (assume x13=x3). So there are at most five yi which are equal to 17; WLOG assume y1=y3=y5=y7=y9=17. This causes y2,y4,y6,y8,y10≤16. However, since ∑yi=165, y2+y4+y6+y8+y10=80, so y2=y4=y6=y8=y10=16. Now, note that x1=x4+1, and x4=x7−1 by comparing y1 against y2 and y4 against y5. This means x1=x7, contradiction. So a cannot be equal to 17, contradiction. Now, this leaves us with the necessity of the proof that a≤18. Note the following arrangement: 10 1 7 9 2 6 4 8 3 5 No three consecutive numbers has a sum of larger than 18, so a≤18. So the maximum value of a is 18.
01.07.2011 02:41
There is a much simpler argument for a≥18. The other nine numbers than 1 form three groups of three adjacent numbers each, of total sum 54=3⋅18, so (at least) one of the grup sums to (at least) 18.
11.07.2011 17:40
Yes, mavropnevma, that was official solution. My was same as the one of chaotic_iak.
15.12.2013 04:50
RaleD wrote: Find maximum value of number a such that for any arrangement of numbers 1,2,…,10 on a circle, we can find three consecutive numbers such their sum bigger or equal than a. Find maximum value of number a such that for any arrangement of numbers 1,2,…,10 on a line, we can find three consecutive numbers such their sum bigger or equal than a ?.