The discussion revolves around the arrangement of m men and n women such that no two women are adjacent. The participants explore combinatorial methods to solve this problem, with the condition that m is greater than n.
The discussion is active, with multiple interpretations being explored. Some participants have offered guidance on potential methods, while others express confusion about certain aspects of the reasoning. There is no explicit consensus on a single approach yet.
Participants note that the problem likely refers to a linear arrangement rather than a circular one. There is also mention of the need to clarify the constraints regarding the placement of women in relation to the gaps created by the men.
It doesn't say, but this seems to refer to arrangement in a straight line, not a circle.Yashbhatt said:In how many ways can m men and n women be arranged such that no two women are besides each other?
(m > n)
haruspex said:It doesn't say, but this seems to refer to arrangement in a straight line, not a circle.
I approach this class of problems by reducing to one that has no such constraint.
First, treat men as identical and women as identical. We can fix that up later by multiplying by the appropriate factorials.
Suppose you have a valid arrangement. The women in the line partition the set of men into subsets (how many?). What constraint is there on the size of each subset (it's not the same for all of them)? Where the constraint is >= 1, throw a man away. How many men are left? How many ways are there of carving them into the right number of partitions of >= 0 each?
To show the technique is valid, you need to see that there is a 1-1 mapping between solutions to the reduced problem and those to the original one. We have the mapping one way. To go the other, just insert one man into every partition that should have at least one.
Yes, that's an excellent method - though I didn't understand the bit "if there are any women on those imaginary gaps, shift them in". What is meant by shifting them in? Seems to me the job is done.Yashbhatt said:A friend told me this approach : First, let us consider filling all the men. We will fill them with a gap between each one of them so that we can fill the women there. Now, if we fill them in such a way, there will be m - 1 gaps. Now, add two imaginary places at each end. So, now there are m + 1 places. Fill the women in those places and if there are any women on those imaginary gaps, shift them in and in this way we will reach the answer.
Is that correct?
haruspex said:Yes, that's an excellent method - though I didn't understand the bit "if there are any women on those imaginary gaps, shift them in". What is meant by shifting them in? Seems to me the job is done.
Yashbhatt said:It is to simplify things. Like after all those gaps are imaginary. So, if you have placed the first man on the first seat and then all others with a gap in between, you don't have to work what will be the case then. Just first arrange the women in the seats including the imaginary ones. If you place them on the imaginary ones, then there will be places in between which are empty because m + 1 > n. So, now shift them from the imaginary ones to the empty real ones.
PeroK said:I don't follow this logic. The way I'd look at it is. First, you place the n men:
- M - M - M ... - M -
Each dash (-) represents a place where a woman could stand. There are (n+1) such places and m women, so ##\binom{n+1}{m}## possibilities.
Yashbhatt said:Yes. That is what I am trying to say.
And according to the question it is P(m + 1, n) and not P(n + 1, m).