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. 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. How many ways can the Earthlings and Martians be seated around the round-table?
Problem
Source: Bangladesh National Mathematical Olympiad 2016
Tags: Bdmo, combinatorics, permutations, circle, contests
anonman
16.03.2019 11:53
$bump$ ...
chem123
16.03.2019 12:25
1. Simple:Place the earthlings first. $ \implies m!$ ways. Now, there are $m+1$ gaps. Hence, place n martians in that .$\implies \binom{n}{m+1}$ So, $m! \binom{n}{m+1}$ ways. Note that $n>m+1$
chem123
16.03.2019 12:26
For a round table. $m! \to (m-1)!$ $\binom{n}{m+1} \to \binom{n}{m}$ So, $(m-1)! .\binom{n}{m}$ ways
anonman
17.03.2019 06:46
chem123 wrote: 1. Simple:Place the earthlings first. $ \implies m!$ ways. Now, there are $m+1$ gaps. Hence, place n martians in that .$\implies \binom{n}{m+1}$ So, $m! \binom{n}{m+1}$ ways. Note that $n>m+1$ in the first line , why $m!$ ways,earthlings are $n$ numbered.so wouldn't that be $n!$?
anonman
17.03.2019 09:55
why not $2$, will be $(m-1)! \times n!$ ? you may seee: https://artofproblemsolving.com/community/c3h1804185_boys_and_girls
chem123
17.03.2019 10:19
Sorry. In all my answers, interchange $m$ and $n$.
Richie
17.03.2019 14:36
The answer is $\boxed{n!\times\binom{n+1}{m}\times m!}$ Note that $n+1\geq m$
The answer is $\boxed{(n-1)!\times\binom{n}{m}\times m!}$ Note that $n\geq m$
anonman
17.03.2019 15:14
Richie wrote:
The answer is $\boxed{n!\times\binom{n+1}{m}\times m!}$ Note that $n+1\geq m$
The answer is $\boxed{(n-1)!\times\binom{n}{m}\times m!}$ Note that $n\geq m$
can you please explain? that will be really helpful
anonman
18.03.2019 15:18
how is there are always $n$ and $n+1$ gaps between earthligs????? Please help
Purple_Planet
18.03.2019 15:32
First let us seat the $m$ Martian. Now, the Martians can be arranged in $m!$. So, there are $m+1$ places for seating the earthlings with at least one in each place and so this can be done in $\binom{n-1}{m}$. Now, each earthling can be arranged in $n! $ ways. So, in total we have $$m!\times n!\times \binom{n-1}{m}.$$(Note that $n-1\ge m$)
Similarly, you can show that the number of ways is $(m-1)! \times n! \times \binom{n-1}{m}$ (Note that $n-1\ge m$)
anonman
18.03.2019 16:37
So, there are $m+1$ places for seating the earthlings with at least one in each place and so this can be done in $\binom{n-1}{m}$ don't understand,can u please explain deeply
Richie
18.03.2019 21:41
Hate to say it, but Purple_Planet 's answer and solution are wrong. We should first place the earthlings not the martians. Here is my solution.
First place those $n$ earthlings in a line. This can be done in $n!$ ways. Now there are $n+1$ gaps in which we have to place the $m$ martians, where each gap can have at most $1$ martian. This can be done by $\binom{n+1}{m}\times m!$ ways. So our final answer becomes $\boxed{n!\times\binom{n+1}{m}\times m!}$. Note that $n+1\geq m$. We can check that this formula is correct by studying simple cases. Let $m=2$ and $n=1$. This means there are $2$ martians and $1$ earthling. Let those martians be $M_1$ and $M_2$. Let the earthling be $E$. Clearly this can be done in $2$ ways viz $M_1 E M_2$ and $M_2 E M_1$. Plugging the values of $m$ and $n$ in our formula we get $1!\times \binom{2}{2}\times 2!=2$ which we got by counting as well. So our formula is verified to be correct. But according to Purple_Planet the answer should be zero which is clearly false as I have showed the $2$ possible ways.
This is similar to first one. First place those $n$ earthlings in a circle. This can be done in $(n-1)!$ ways. Now there are $n$ gaps in which we have to place those $m$ martians such that each gap can have at most $1$ martian. Again this can be done in $\binom{n}{m}\times m!$ ways. So our final answer becomes $\boxed{(n-1)!\times\binom{n}{m}\times m!}$. Note that $n\geq m$. We can again verify this formula is correct by taking the simple case which I took in first problem.
anonman
19.03.2019 10:41
I understand everything except in $a$ you said that then there are $n+1$ gaps in which we have to place the martians. But will there always be $n+1$ gaps ? like in the picture, there are $n-1$ gaps placing $2$ earthlings at the start and end of the line.what do you think? OMG,it's $500$ th post!!!
Attachments:
Richie
19.03.2019 10:50
The Martians can also sit to the left of the first Earthling and also to the right of the last Earthling like this below:- $$M E M E E M$$
anonman
19.03.2019 10:53
Richie wrote: The Martians can also sit to the left of the first Earthling and also to the right of the last Earthling like this below:- $$M E M E E M$$ but wasn't that meant to be the end and starting point of the line? then how can you place martinas left of the first earthling and to right of the last earthling? then wouldn't it go outside the line?
Richie
19.03.2019 10:58
There is nothing mentioned about whether the line must start and end with an Earthling. So we can put the Martians at the two extreme ends as well.
anonman
19.03.2019 10:59
okay,thank you very much!