Results 1 to 15 of 15
Like Tree5Thanks
  • 2 Post By Idea
  • 1 Post By Plato
  • 2 Post By hedi

Thread: Arrangments in a circle

  1. #1
    Member
    Joined
    Oct 2012
    From
    israel
    Posts
    221
    Thanks
    17

    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)
    Thank's in advance
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    11,344
    Thanks
    828
    Awards
    1

    Re: Arrangments in a circle

    Quote Originally Posted by hedi View Post
    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)
    Thank's in advance
    What have you tried?

    -Dan
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Oct 2012
    From
    israel
    Posts
    221
    Thanks
    17

    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.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member
    Joined
    Oct 2012
    From
    israel
    Posts
    221
    Thanks
    17

    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.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Dec 2018
    From
    Europe
    Posts
    3

    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.
    Last edited by NeonCloud; Dec 28th 2018 at 03:51 AM.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Member
    Joined
    Oct 2012
    From
    israel
    Posts
    221
    Thanks
    17

    Re: Arrangments in a circle

    But we need to prove it in every circle arrangement
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Newbie
    Joined
    Dec 2018
    From
    Europe
    Posts
    3

    Re: Arrangments in a circle

    Quote Originally Posted by NeonCloud View Post
    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).

    Quote Originally Posted by hedi View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Super Member
    Joined
    Jun 2013
    From
    Lebanon
    Posts
    932
    Thanks
    461

    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$

    add them up

    $\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 $

    contradiction
    Thanks from Plato and topsquark
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Newbie
    Joined
    Jun 2018
    From
    Dimona
    Posts
    23

    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?
    Last edited by yyakob; Dec 29th 2018 at 07:10 AM.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    MHF Contributor

    Joined
    Aug 2006
    Posts
    22,209
    Thanks
    3111
    Awards
    1

    Re: Arrangments in a circle

    Quote Originally Posted by yyakob View Post
    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.
    Thanks from topsquark
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Member
    Joined
    Oct 2012
    From
    israel
    Posts
    221
    Thanks
    17

    Re: Arrangments in a circle

    Yes,i arrived to this solution also.
    Thank's
    Last edited by hedi; Dec 29th 2018 at 05:41 PM.
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Newbie
    Joined
    Jun 2018
    From
    Dimona
    Posts
    23

    Re: Arrangments in a circle

    Quote Originally Posted by Plato View Post
    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?
    Last edited by yyakob; Dec 31st 2018 at 05:45 PM.
    Follow Math Help Forum on Facebook and Google+

  13. #13
    Member
    Joined
    Oct 2012
    From
    israel
    Posts
    221
    Thanks
    17

    Re: Arrangments in a circle

    you need to show it for EVERY circle arrangement.
    Thanks from Plato and topsquark
    Follow Math Help Forum on Facebook and Google+

  14. #14
    MHF Contributor

    Joined
    Aug 2006
    Posts
    22,209
    Thanks
    3111
    Awards
    1

    Re: Arrangments in a circle

    Quote Originally Posted by yyakob View Post
    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?
    Last edited by Plato; Dec 31st 2018 at 06:40 PM.
    Follow Math Help Forum on Facebook and Google+

  15. #15
    Newbie
    Joined
    Dec 2018
    From
    India
    Posts
    16
    Thanks
    5

    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
    Last edited by mak29; Jan 3rd 2019 at 07:07 AM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Finding different arrangments
    Posted in the Algebra Forum
    Replies: 1
    Last Post: Jul 8th 2012, 12:38 AM
  2. [Combinations//Permutations] Item Arrangments
    Posted in the Statistics Forum
    Replies: 2
    Last Post: Aug 16th 2010, 05:09 AM
  3. Replies: 6
    Last Post: Jul 8th 2010, 06:39 PM
  4. different arrangments number of ways
    Posted in the Statistics Forum
    Replies: 3
    Last Post: Dec 3rd 2008, 11:15 PM
  5. arrangments
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Aug 13th 2008, 05:52 AM

/mathhelpforum @mathhelpforum