0
$\begingroup$

Suppose there are 6 couples that go to a party, at the party they are given hats in such a way that no female can wear the same color (and males can't wear the same color).

So you have 6 pairs of hats (yellow, yellow, red, red etc.) and you want to know the amount of ways in which you can match those so that no female has the same color and no male has the same color. But the catch is NONE of the couples are allowed the same color either.

This is related to the following question: Principle of inclusion and exclusion/ Matching But there is no answer, my teacher used some sort of inclusion/exclusion method in his working out which I personally found confusing, I would appreciate either another method or an layman explanation to how you apply inclusion/exclusion here.

So a little bit of how far I've come with this, I thought that you could take the total amount of ways $ 6! \times 6! $ and then subtract/divide by the amount of ways which don't satisfy the conditions.. but I'm having trouble getting anywhere because the number changes depending on how you distribute the hats..

$\endgroup$
0
$\begingroup$

Place six dots in a row, then six dots underneath, also in a row. Each way to distribute the hats corresponds to

  • a way to join each dot from the top to some dot from the bottom, but not the one directly underneath.
  • a choice of a colour for each of the six strands so formed.

The first choice corresponds to a derangement of a set of cardinality $6$. The second choice corresponds to a permutation of a set of cardinality $6$.

Therefore the number of options is $$6!\cdot!6=190800$$


From a teaching point of view, if I was to give this exercise to students as part of a Problem Solving course, assuming they have never seen derangements before, I would expect them to replace $6$ with lower numbers, $2, 3, \ldots$, until they observe a pattern and come to the idea of an induction, thus reproving the derangement formula.

$\endgroup$
  • $\begingroup$ That is the correct answer but I'm afraid I'm not familiar with the derangement operator.. I don't think our teacher expects us to have known of that since we didn't learn it in the course and he didn't use it when he went over it either, I'll definitely look into derangement as it seems very interesting but I'm wondering if there is another way to "intuitively" come to the same result? Thank you. $\endgroup$ – Quaz May 24 '18 at 17:09
  • $\begingroup$ @Quaz From the link I gave you you can find several ways to count derangements, all of them can be proved by induction. I can't see a more intuitive way. $\endgroup$ – Arnaud Mortier May 24 '18 at 17:13

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.