1. Limited time only! Sign up for a free 30min personal 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!

Homework Help: 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


    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


    User Avatar
    Science Advisor
    Homework Helper
    2017 Award

    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
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted