How many different solutions are there?

  • Thread starter Thread starter Thiru07
  • Start date Start date
  • Tags Tags
    Combinatorics
Click For Summary

Discussion Overview

The discussion revolves around a combinatorial problem involving the selection of non-neighbouring positive integers from a circular arrangement of numbers 1 to 7. Participants explore methods to determine the number of valid selections without directly listing all combinations.

Discussion Character

  • Homework-related
  • Mathematical reasoning
  • Exploratory

Main Points Raised

  • One participant describes a brute force approach to find the number of valid combinations by listing all possible triplets and eliminating those with adjacent numbers.
  • Another participant suggests that using symmetry could potentially simplify the problem and speed up the solution process.
  • A different participant outlines a reasoning process for selecting numbers, detailing the choices available after picking the first number and how it affects subsequent selections, ultimately arriving at a count of 7 different solutions.
  • There is a reiteration of the brute force method, confirming that it involves calculating all combinations and removing those that do not meet the criteria.

Areas of Agreement / Disagreement

Participants do not reach a consensus on the best method to solve the problem, with some favoring brute force and others suggesting alternative reasoning approaches. The discussion remains unresolved regarding the most efficient solution.

Contextual Notes

The discussion does not clarify the assumptions regarding the adjacency of numbers in the circular arrangement or the implications of symmetry in the problem-solving process.

Thiru07
Messages
41
Reaction score
0

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?
 
Physics news on Phys.org
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.
 
Hi,
Thiru07 said:
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...
 
BvU said:
Hi,
I suppose brute force is writing down all C(7,3) triplets (35) and erasing the ones that have adjacencies...
Exactly.
 

Similar threads

  • · Replies 32 ·
2
Replies
32
Views
5K
  • · Replies 1 ·
Replies
1
Views
925
  • · Replies 2 ·
Replies
2
Views
3K
Replies
33
Views
5K
  • · Replies 21 ·
Replies
21
Views
2K
  • · Replies 27 ·
Replies
27
Views
5K
Replies
1
Views
5K
  • · Replies 12 ·
Replies
12
Views
2K
  • · Replies 8 ·
Replies
8
Views
2K
  • · Replies 2 ·
Replies
2
Views
2K