12
$\begingroup$

I have a very simple combinatorics problem, and I am (almost) sure I did this right. However, the smartest guy in my class thinks different and this made me doubt, so I will post our views to this problem and I would like to know who is right.

In how many different ways can 10 people be seated around a round table, under the condition that there are 5 man and 5 women, and no two males or two females can be seated adjacently.

My view

We number the chairs in an arbitrary way, so the chair numbering is fixed. At chair $1$, there is seated either a man or a woman, which given $2$ possibilities. When we observe the gender of the person in the first chair, the division of the table over the two genders in given. Then there are $5!$ ways to seat the men over the $5$ male chairs and $5!$ ways to seat the women over the $5$ female chairs. So in total this gives $2.(5!)^2$ possibilities.

My classmates view

First all males are seated, which is possible in $5!$ ways. Because no males can sit adjacently and the people are seated in a circle, we can rotate the table and in this way we count all possibilities 5 times too much, so $5!/5=4!$ ways to seat the man. After this, the table division is fixed, but we still have to seat the women. This gives another $5!$ ways, so in total $5!4!$ ways.

What I think is wrong with this view

I don't think the argument about rotation of the table makes any sense. The argument can make sense though, if we use exactly my classmate's argument, but acknowledge that the first person to be seated can be any of the $10$ people, so giving an extra $10$ possibilities. Then proceed as my classmate, giving the same answer as me. However, my classmate does not agree. So who is right?

Also, if we use our arguments to the same problem but a table of $2$ people, one male, one female, there are obviously $2$ possibilities. Then my method gives $2.(1!)^2=2$ possibilities, but my classmate's method gives only $1!0!=1$ possibility.

EDIT

I think the main problem is in different interpretations of the problem, where my interpretation is that it matters who sit at 'chair 1' while my classmates thinks that only the ordering of the people matters. However, given only the above problem, what would be the right interpretation, or is this ambiguous?

$\endgroup$
  • 1
    $\begingroup$ Excluding the one and only genious Václav Mordvinov of course. $\endgroup$ – Václav Mordvinov Jan 10 '18 at 11:10
  • $\begingroup$ Are they seated at/around the table, or "on" the table, as you stated? Sitting 10 people on the table may be tricky. (I am only joking) $\endgroup$ – mbomb007 Jan 10 '18 at 23:09
  • $\begingroup$ Not a native speaker. $\endgroup$ – Václav Mordvinov Jan 10 '18 at 23:10
14
$\begingroup$

Your solution would be okay if there is a "special chair" (you name it "chair $1$"). Then there is no essential difference with placing the $10$ persons in a row in which case there is also a special chair (for instance the utmost left, or the utmost right).

If there is no special chair then you can start by placing one man. After that there are $4!$ different arrangements for the other men and $5!$ different arrangements for the women. This leads to a total of $4!5!$ possibilities.

It is not for nothing that a round table is used, indicating that there is no special chair. So I would say that your classmate is right.

$\endgroup$
  • $\begingroup$ Okay thanks, I think you are right about that my classmate's interpretation is the most natural, otherwise they wouldn't have used a circle in the question. It is still a bit ambiguous but you're right! $\endgroup$ – Václav Mordvinov Jan 10 '18 at 9:51
  • 1
    $\begingroup$ You are welcome. According to your interpretation there are $2$ ways to place one man and one woman at a round table. That is correct if the two chairs are distinguishable, but incorrect if they are not (which is definitely a more likely interpretation). $\endgroup$ – drhab Jan 10 '18 at 9:56
  • 1
    $\begingroup$ The round table could be so that there is no one on the "end" who is exempted from the condition "no two males or two females can be seated adjacently". $\endgroup$ – Acccumulation Jan 10 '18 at 16:48
  • 1
    $\begingroup$ @Acccumulation: If you have five men and five women in a row, with no two adjacent men and no two adjacent women, then it's already guaranteed that the people at the two ends will be one man and one woman. So if that's the only reason they specified a round table, then they needn't have specified it. $\endgroup$ – ruakh Jan 11 '18 at 0:24
  • $\begingroup$ @Acccumulation I fully agree with ruakh $\endgroup$ – drhab Jan 11 '18 at 6:58
5
$\begingroup$

Your disagreement comes from different interpretations of the question.

You're assuming the chairs around the table are indexed ${1,...,10}$ and you're looking at the number of ways to assign the numbers ${1,...,10}$ to your 5 men and 5 women.

Your classmate is looking at how many ways you can arrange 5 men and women around the table relative to each other instead of in absolute terms.

The difference between the two answers is a factor of 10 ($10\times4!5! = 2\times 5 \times 4!5! = 2\times(5!)^2$), which corresponds to the extra degree of freedom (e.g. where is chair #1).

$\endgroup$
  • $\begingroup$ Good answer! Thanks $\endgroup$ – rae306 Jan 10 '18 at 19:46
4
$\begingroup$

The thing is, that when you are a circle, each combination $x_1, x_2 \dots x_{10}$ is counted $10$ times, namely

$x_1, x_2 \dots x_9 x_{10}$,

$x_2, x_3 \dots x_{10},x_1$,

$x_3, x_4 \dots x_1, x_2$,

$\dots$

$x_{10}, x_1, \dots x_8, x_9$

since rotating the table preserves the combination of people sitting

In the case of $2$ people you get the combinations:

man, woman

woman, man

but they are essentially the same.

Your edit is spot on, depends on whether the chairs differ from one another, but it'd assume that this is not the case

$\endgroup$
  • $\begingroup$ Yes, but why wouldn't it matter who sits at chair 1? See also my edit. Is this really obvious from the problem? I understand completely what you are saying but to me the question seems ambiguous. $\endgroup$ – Václav Mordvinov Jan 10 '18 at 9:22
  • $\begingroup$ @VáclavMordvinov We all passed through that. Yes, it's ambiguous, but with time you will start to see what they want with this kind of questions. Not that it will ever change, but you will get used to it, and you will see that it's not “ambiguous” once you know how they speak. But yes, you are right, that way to phrase problems is not ideal and ambiguous to a random reader. We all passed that phase at which we had a problem with probability problems badly written. Good luck. $\endgroup$ – Manuel Jan 10 '18 at 14:21
  • $\begingroup$ @Manuel, you're right, especially since it is a problem and not a real-life application. I just have to read better next time :) $\endgroup$ – Václav Mordvinov Jan 10 '18 at 18:29
  • $\begingroup$ @VáclavMordvinov "Read better", yes, but do not forget that you are right now thinking it's badly written. I meant that sadly it's badly written, but it's not the worst, you just have to get used to it. $\endgroup$ – Manuel Jan 10 '18 at 18:31
  • $\begingroup$ Yes, generally I add what I assume for such a question and if necessary I include multiple answers for multiple assumption sets. It's not that much more effort and yields the rigjt answer for sure. $\endgroup$ – Václav Mordvinov Jan 10 '18 at 18:37
4
$\begingroup$

In combinatorics, the definition of "different" is often a crucial issue. There is nothing in the problem saying that the chairs are interchangeable, and you should not add assumptions to the problem. If I were only one person to be seated, I would have ten choices where to sit. Your interpretation is the correct one. If your classmate's interpretation were intended, then the problem is poorly stated.

And actually, if we to follow your classmate's reasoning, then why stop there? Your classmate is noting that rotation leaves the arrangement "essentially" the same, but what about reflections? If all that matters is who is sitting next to whom, and absolute location is unimportant, then wouldn't the answer be 5!4!/2?

$\endgroup$
  • $\begingroup$ Good answer, I will send this to him too :) $\endgroup$ – Václav Mordvinov Jan 10 '18 at 18:34
  • $\begingroup$ If you were the only person to be seated, you could actually tell that there is only one resulting configuration, if the table is ROUND with no orientation mark $\endgroup$ – G Cab Jan 11 '18 at 2:08
  • $\begingroup$ @G Cab Yes, if the table is a non-rotating, uncharged black hole in otherwise empty space, then all locations are indistinguishable. If, on the other hand, this takes place in the real world ... $\endgroup$ – Acccumulation Jan 11 '18 at 3:15

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.