# Thread: Arrangments in a circle

1. ## Arrangments in a circle

prove that in every circle arrangment of {1,2,...n} there exists three consecutive elements (three neibours in the cycle arrangement) whose sum is at least [3(n+1)/2], (the upper integer value)

2. ## Re: Arrangments in a circle

Originally Posted by hedi
prove that in every circle arrangment of {1,2,...n} there exists three consecutive elements (three neibours in the cycle arrangement) whose sum is at least [3(n+1)/2], (the upper integer value)
What have you tried?

-Dan

3. ## Re: Arrangments in a circle

I think I solve it but I want to see other solutions.I showed that the number C(n,3) of possible three numbers is larger than the number of sums that are smaller than the given sum.

4. ## Re: Arrangments in a circle

No, this is not the solution.Rather ,the given number is the average of all sums of three neighbours in every circle arrangement so if one sum is smaller there must be a sum 5that is greater.

5. ## Re: Arrangments in a circle

Forgive me if I have misunderstood something but I think the "trick" is to realize that the highest sum of three consecutive elements is n(n-1)(n-2)/3. And then you just need to prove that this sum is at least as big as 3(n+1)/2.

6. ## Re: Arrangments in a circle

But we need to prove it in every circle arrangement

7. ## Re: Arrangments in a circle

Originally Posted by NeonCloud
the highest sum of three consecutive elements is n(n-1)(n-2)/3.
Not sure what I was thinking here. The highest sum is of course n+(n-1)+(n-2).

Originally Posted by hedi
But we need to prove it in every circle arrangement
I assume the smallest possible value of n is 3. If you can prove it for n=3, then it shouldn't be hard to prove it for the rest.

8. ## Re: Arrangments in a circle

Suppose there is a circle arrangement

$\displaystyle a_1,a_2,a_3,\text{...},a_n,a_1,\text{...}$

for which this is not true. This means

$\displaystyle a_1+a_2+a_3\leq \left\lceil \frac{3(n+1)}{2}\right\rceil -1$
$\displaystyle a_2+a_3+a_4\leq \left\lceil \frac{3(n+1)}{2}\right\rceil -1$
$\displaystyle .$
$\displaystyle .$
$\displaystyle .$
$\displaystyle a_n+a_1+a_2\leq \left\lceil \frac{3(n+1)}{2}\right\rceil -1$

$\displaystyle 3\sum _{i=1}^n a_i\leq n \left\lceil \frac{3(n+1)}{2}\right\rceil -n$

$\displaystyle \frac{3n(n+1)}{2}\leq n \left\lceil \frac{3(n+1)}{2}\right\rceil -n$

$\displaystyle \frac{3(n+1)}{2}+1\leq \text{ }\left\lceil \frac{3(n+1)}{2}\right\rceil$

9. ## Re: Arrangments in a circle

If a1, a2, a3 are consecutive element number - the average is always* a2.
O.K.

(a1+a2+a3)/3 = a2*

* Remember: the result is the upper integer value Case

Why?

10. ## Re: Arrangments in a circle

Originally Posted by yyakob
If a1, a2, a3 are consecutive element number - the average is always* a2.

(a1+a2+a3)/3 = a2*
* Remember: the result is the [COLOR=#FF8C00]upper integer value Case
I think this has been a greatly misunderstood problem.
Suppose that $N=12$ The question is about circular arrangements of which there are $11!$ possible.
Further of all those possible arrangements show that every one of them contains three neighbors $\displaystyle {a_k} + {a_{k + 1}} + {a_{k + 2}} \ge \left\lceil {\frac{{3(N + 1)}}{2}} \right\rceil$
In the case $N=12$ that number is $20$, so if $\displaystyle {a_k}=10, ~ {a_{k + 1}}=2 ,~\&~ {a_{k + 2}}=5$ those neighbors add to $17$ so they do not work.
Look at Idea's solution to see a really innovative proof.

11. ## Re: Arrangments in a circle

Yes,i arrived to this solution also.
Thank's

12. ## Re: Arrangments in a circle

Originally Posted by Plato
I think this has been a greatly misunderstood problem.
Suppose that $N=12$ The question is about circular arrangements of which there are $11!$ possible.
Further of all those possible arrangements show that every one of them contains three neighbors $\displaystyle {a_k} + {a_{k + 1}} + {a_{k + 2}} \ge \left\lceil {\frac{{3(N + 1)}}{2}} \right\rceil$
In the case $N=12$ that number is $20$, so if $\displaystyle {a_k}=10, ~ {a_{k + 1}}=2 ,~\&~ {a_{k + 2}}=5$ those neighbors add to $17$ so they do not work.
Look at Idea's solution to see a really innovative proof.
Why my solution don't show the solution of the (first + second + third) as In your formula?
What is the reason that I wrong?!

It is possible to show that the sum is lesser because of this... how I called it... similar to "identity". Not?

13. ## Re: Arrangments in a circle

you need to show it for EVERY circle arrangement.

14. ## Re: Arrangments in a circle

Originally Posted by yyakob
Why my solution don't show the solution of the (first + second + third) as In your formula?
What is the reason that I wrong?! It is possible to show that the sum is lesser because of this... how I called it... similar to "identity". Not?
I point out to you that this is an English Language website. You are welcome here as long as you know that.
I fear that I am not sure that I understand what you wrote. That said take my example in which $N=12$ that is arranging the numbers $\{1,2,3,\cdots,11,12\}$ in a circular pattern: a random analog clock face. That are $11!=39,916,800$ ways to do that. This question asks you to prove the in each of those almost forty million arrangements there are three neighbors whose sum is at least $\left\lceil {\frac{{3(11 + 1)}}{2}} \right\rceil$. Actually you are asked to prove this in general not just for one value of $N$. Now maybe you miss-read the question written in English?

15. ## Re: Arrangments in a circle

It can be successfully solved with the 'Principle Of Mathematical Induction'.

As we know the smallest circle can be formed with 3 positions(numbers in this case.)

Step 1:Prove for the smallest circle that it is true-

Sum of elements=3+2+1=6
which is =3(n+1)/2=6
So it is true for n=3;smallest circle

Step 2:Let it be true for n=m;
,i.e., m+(m-1)+(m-2)>=3(m+1)/2
=> 3m-3>=3(m+1)/2=(3m+3)/2

Step 3:Now prove that it will be true for n=m+1;
,i.e., (m+1)+m+(m-1)=3m
we need to prove that it greater 3(m+2)/2=(3m+6)/2=(3m+3)/2+(3/2)
In the LHS the sum increased by 3 whereas in the RHS only by 3/2. (as compared to n=m);
so,definitely this property is true for n=m+1
This way we can prove that for any two consecutive numbers it is true;i.e.,true for entire +ve integer system>3