How many different solutions are there?

[Thiru07]

Homework Statement

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?

Homework Equations

C(n,r) = n! / (r! * (n-r)!)

The Attempt at a Solution

Brute force.

Is there a quicker method to solve this problem?

 

[gneill]

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.

 

[BvU]

Hi,

Is there a quicker method to solve this problem?

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

 

[Thiru07]

Hi,
I suppose brute force is writing down all C(7,3) triplets (35) and erasing the ones that have adjacencies...

Exactly.