2
$\begingroup$

Six people are given numbers $1$, $2$... $6$.They are to be seated on a round table. What is the probability that the sum of any two two adjacent people is not 7. My approach : I sat people $4$,$5$,$6$ in two ways.

Case $1$- only one person in the gaps. There is only one way in this to sit the complementary number opposite to each of 4,5,6.

Case$2$- (Two people in a gap, one in another gap)

Choose any gap for the two people. There is a subcase. Suppose our gap is opposite to person 6 ,then person 1 has to mandatorily be one of the two people in the gap to avoid being near 6. Also 1 and his partner (2/3) have exactly one way to sit in the gap to avoid the partner's complentary . So there are $3×2 = 6$ ways in here.

Case$3$- (3 people in a gap ) Here there are $3$ ways to select the gap. Then a further $3$ ways to seat them(for which I listed out the 6 ways to sit in a gap) So 9 ways here.

Total of $2×16$ ways, which gives a probability of $32/120= 4/15$

My query here is that wether a more elegant approach is possible , as it would be required for an extended problem of seating 8 people on a round table , such that no two have an adjacent sum of $9$. This above method leads to formation of to many cases for the 8 people problem.

Could a general solution for 2n people be found by that method?

$\endgroup$
4

1 Answer 1

1
$\begingroup$

You are trying to count the number of hamiltonian cycles in the complement of a graph $G$, where $G$ is a matching with $m$ edges.

The number of such cycles can be obtained via inclusion exclusion.

If you have a set of $i$ edges that must appear in the cycle, we can count them by combining the two vertices in each edge and choosing the order of these two edges. So you get the expression for counting cyclic permutations with $n-i$ objects, multiplied by $2^i$, which is $(n-i-1)!2^i$.

Once you have this preliminary formula you can just use normal inclusion-exclusion to count the cycles that avoid all of the edges:

$\sum\limits_{i=0}^m (-1)^i\binom{m}{i} [(n-i-1)! 2^i]$

In our case $n=6,m=3$ so we get $120-144+72-16 = 32$.

We have $32/5! = 4/15$

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.