Suppose there are $m$ Martians and $n$ Earthlings at an intergalactic peace conference. To ensure the Martians stay peaceful at the conference, we must make sure that no two Martians sit together, such that between any two Martians there is always at least one Earthling.
(a) Suppose all $m+n$ Martians and Earthlings are seated in a line. In how many ways can the Earthlings and Martians be seated in a line?
(b) Suppose now that the $m+n$ Martians and Earthlings are seated around a circular round-table. In how many ways can the Earthlings and Martians be seated around the round-table?
Source: BdMO 2016 National Secondary P5
The idea is to first make the Earthlings sit, then make the Martians sit in the gaps between two Earthlings.
a)
There are $n!$ ways in which the Earthlings can sit. After they sit, there are $n+1$ ($n-1$ gaps between two Earthlings and $2$ positions at the sides) empty positions for the Martians to sit. There are $^{n+1}P_{m}=m!\binom{n+1}{m}$ ways for the $m$ Martians to sit in $n+1$ positions. Therefore, the answer is $\boxed{m!\cdot n!\cdot\tbinom{n+1}{m}}$.
b)
There are $(n-1)!$ ways for the Earthlings to sit around a round-table. But this time, there are $n$ positions for the Martians to sit. There are $^{n}P_{m}=m!\binom{n}{m}$ ways in which the Martians can sit. Hence, the total number of ways is $\boxed{m!\cdot(n-1)!\cdot\tbinom{n}{m}}$.
Place the Earthlings first and then place the Martians in the gaps.
Gonitzoggoβ