1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

How many different solutions are there?

  1. Nov 16, 2016 #1
    1. The problem statement, all variables and given/known data
    If we want to use positive integers from 1 until 7 to form a ring in order. Since 1 and 7 are adjacent to each other in the ring. Due to their neighbouring position, 1 and 7 are also considered as neighbour numbers. Then if we want to pick 3 non-neighbouring numbers from this ring of 7 numbers, how many different solutions are there?

    2. Relevant equations
    C(n,r) = n! / (r! * (n-r)!)

    3. The attempt at a solution
    Brute force.

    Is there a quicker method to solve this problem?
     
  2. jcsd
  3. Nov 16, 2016 #2

    gneill

    User Avatar

    Staff: Mentor

    What's your brute force solution? How did you implement it?

    It's hard to evaluate the relative effort involved in alternative solutions if we don't know what the benchmark is. But without going too far out on a limb I think it's safe to say that a judicious use of symmetry should speed things up considerably.
     
  4. Nov 16, 2016 #3

    BvU

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    Hi,
    Reasoning ?

    I can pick #1 in 7 ways. Eliminates 2 neighbours. Leaves 4, of which two are at a distance 2 and two at a distance 3.
    If I pick #2 as one of the two numbers at distance 2, I still have 2 choices for #3. So 4 possibilities.
    If I pick #2 as one of the two numbers at distance 3, the last choice is dictated. So 2 possibilities.

    7 x 6 has to be divided by 3! for the order in which I pick is arbitrary. Leaves 7 different solutions.

    I suppose brute force is writing down all C(7,3) triplets (35) and erasing the ones that have adjacencies...
     
  5. Nov 16, 2016 #4
    Exactly.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted