Friday, April 6, 2012
JCCDQBHWHCB002(iii) Combinatorics : Partitioning and team shuffling
Suggested Approaches and Solutions:-
Though not compulsory, a diagram is very useful to help visualise the situation.
There are three subgroups, with sizes 1,1,2. Let’s call them teams A, B, and C. Within each team, the order of individual members does not matter. However, human beings are deemed to have distinct identities.
Now, how many ways are there to partition the ladies into the above three teams? Think of an equivalent problem (another heuristic): Imagine the ladies lining up and then put on T-shirts, with letters A, B, C, C for the teams. So how many words can you spell with four letters, two of which are repeated?
Number of ways to partition the ladies into the three teams = 4! / 2!
Number of ways to put the men into the teams = 3!
Note that teams A and B, which have the same number of people, are interchangeable (the team names do not matter, but rather who gets teamed up with who), so we need to divide by 2!
So the answer is
4! / 2! x 3! x 1 / 2! = 36
Are there other methods or ways to think about this problem?
Yes! Having different methods that give you the same answer increases your confidence that the answer is correct. If you have different answers, try to find out why. You might learn something valuable!
Method 2 (“Phantom” or “Joker” method)
Imagine that, in lieu of the missing guy, we have a ghost (or a Joker card). We try to pair up the ladies with the men (or ghost) as usual, and there are 4P4 = 4! = 4 x 3 x 2 x 1 = 24 ways to do this. The lucky/unlucky lady who got the ghost or Joker card joins one of the 3 actual men. So there are 24 x 3 = 72 ways … Ooops! Why is this not the same as the above method? That is because in each case, the other lady who ended up with the same guy could have been the one that had the Joker card and this possibility was already counted. That means we have uniformly over-counted by exactly a factor of 2! = 2, so we must divide by this number. Thus the correct calculation using this approach is
4! x 3 / 2! = 36
Method 3 (MCP method)
Here I shall use a Multi-stage Combination Product method. Just kidding. There is no such term. Actually MCP means “Must Choose Properly” for Male Ch….. P... We first arrange the guys in order.
Number of ways to choose the “lucky” guy with 2 ladies = 3C1 = 3
Number of ways to choose the “lucky” 2 ladies = 4C2 = 6
Number of ways to shuffle the other 2 ladies = 2! = 2
Total number of ways = 3 x 6 x 2 = 36