0
$\begingroup$

The problem statement goes something like this

How many ways are there to arrange $6$ girls and $15$ boys in a circle such that there are at least two boys between any two adjacent girls?

Here is how I tried to solving it.

  1. I started by first arranging girls in $(6-1)!$ ways.
  2. Next I decided to arrange $6$ boys out of $15$ in the gap between the arranged girls.
  3. Again I did the same for remaining $9$ boys.
  4. Finally, choose $3$ out of $6$ gaps for arranging the remaining $3$ boys.

Altogether, I got $$5! \cdot {{15}\choose{6}} \cdot 6! \cdot {{9}\choose{6}} \cdot 6! \cdot {{6}\choose{3}} \cdot 3!$$

From $(2)$ and $(3)$ I could say that there are at least two boys in between two adjacent girls.

Since I do not have the solution of this problem, I am really not sure about my approach. Am I making a sensible argument? Any help would be appreciated.

$\endgroup$
2
$\begingroup$

Your answer is incorrect since it only allows for gaps of size 2 and 3 and no other size gaps. You will never have a gap of size 5 for example despite that being a possible valid arrangement, e.g. $gbbgbbgbbgbbgbbgbbbbb$ arranged in a circle. As a result, you have undercounted.

For a correct approach, begin by designating one of the girls as being special (for example, the shortest girl). Describe all circular arrangements of the table instead as arrangements in a row where our special girl is furthest left in the row.

We will have something along the lines of an arrangement like:

$$\color{red}{G}(b\dots b)G(b\dots b)G(b\dots b)G(b\dots b)G(b\dots b)G(b\dots b)$$

Let $x_1,x_2,x_3,x_4,x_5,x_6$ represent the number of boys in each of the respective gaps above. Choose a solution $(x_1,x_2,x_3,x_4,x_5,x_6)$ from among the solutions to the system:

$$\begin{cases} x_1+x_2+x_3+x_4+x_5+x_6=15\\ 2\leq x_i~~\forall i\end{cases}$$

Once having chosen a solution $(x_1,x_2,\dots,x_6)$, arrange the boys in a line and have the remaining five girls in a line (remember that we specified our special girl must have been the first in the row) and have them line up according to the pattern we designated.

Apply multiplication principle and conclude.

To count the number of solutions to the system, consider a change of variable $y_i=x_i-1$ to instead be counting the solutions to the system $\begin{cases} y_1+y_2+\dots+y_6=9\\1\leq y_i~~\forall i\end{cases}$ and then apply a stars-and-bars argument.

$~$

There are $\binom{8}{5}$ choices for solution to the system, $5!$ ways to arrange the remaining girls and $15!$ ways to arrange the boys, giving a grand total of $\binom{8}{5}\cdot 5!\cdot 15!$ arrangements.

$\endgroup$
  • $\begingroup$ This indeed is a very nice solution to this problem. It is not like I am trying to be obsessed with my work, but I still would like to know, whether there is a way to cover that undercounted part and will that be enough to reach the right answer. $\endgroup$ – Prateek Apr 24 '17 at 21:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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