# Homework Help: How many different solutions are there?

Tags:
1. Nov 16, 2016

### Thiru07

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. Nov 16, 2016

### 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.

3. Nov 16, 2016

### BvU

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...

4. Nov 16, 2016

Exactly.