JCCDQBHWHCB007(ii) Combinatorics : “Choose, then Automatically fill” technique

     The question says “the captain must stand between the two youngest players” which I interpret literally to mean: not necessarily directly next to each other, but there can be intervening players.  Although I suspect that the one who set this question might have meant that the captain is supposed to be in between directly next to the two youngest players, I shall attempt the question according to its prima facie meaning.  Later, I shall consider what if the captain and two youngest players are together next to one another with the captain in the middle.

Suggested Approach and Solution:-

 

Number of rows to choose from = 2

The condition that “the captain must stand between the two youngest players” seems difficult, because there can be one or more intervening players.  Generally we do not favour complicated case-by-case analyses.  The good news is that we can use a “choose, then automatically fill” technique to tackle this.  Within the row with the captain, there are 5 positions and we choose 3 of them.  Then we automatically fill them with a youngest player, the captain and then the other youngest player.  The number of ways to do this is  ⁵C₃ = 10.

Number of ways the two youngest players can swap around = 2!.

Number of ways the rest of the players can shuffle around   = 7!.

Total number of ways = 2 x ⁵C₃ x 2! x 7! = 201 600.

What if …

     What if the captain is in between directly next to the two youngest players?

 

Number of rows to choose from = 2

     If the captain is in between and directly beside the two youngest players, we treat these 3 players as a unit.  There are ³C₁ = 3 ways to position this group within the row.  Note that within this group, the two youngest players can still swap around while the captain stays in their middle.  Everything else is the same as above.

Total number of ways = 2 x ³C₁ x 2! x 7! = 60 480.

JCCDQBHWHCB007(i) Combinatorics : Choosing with special conditions

     This sort of question has appeared in the GCE ‘A’ levels before.  For questions with special conditions, a good approach is to consider to the special conditions first.

Suggested Approach and Solution:-

 

Number of ways to choose the young player = ²C₁ = 2

The captain must be in, so two vacancies have been taken up and there are 3 left.  These places must be filled from the 7 eligible other players (excluding the captain and the two youngest players).  There are   ⁷C₃ = 35  ways to do this.  The total number of ways is

          35 x 2 = 70

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 ¹ / _2! = 36

Reflection

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  ⁴P₄  = 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 = ³C₁ = 3

Number of ways to choose the “lucky” 2 ladies                = ⁴C₂ = 6

Number of ways to shuffle the other 2 ladies                    = 2!   = 2

Total number of ways = 3 x 6 x 2 = 36

JCCDQBHWHCB015 Combinatorics : Conditional Over-counting

Introduction

     This question is particularly challenging, because it does not conform to any of the usual types of problems taught at ‘A’ level.  However, we can still use the following problem solving heuristics:-

     · drawing a diagram

     · considering a simpler problem first

Suggested Approach and Solution:-

     Consider first the case for 3 couples and draw a diagram with arrows.

Suggested Approach and Solution:-

     We use the same problem-solving tactics as for question 11.  Consider first the case for 3 couples and draw a diagram with arrows.

 

We now discover that this problem is a little more complicated than that of question 11. 

Each of the 3 men has arrows coming out to 2 x 3 – 2 = 4 persons (everyone except himself and his wife).  So there are 3 x (2 x 3 – 2) = 12 arrows.  There is double-counting (arrows in both directions), but only among the men.  So we need to subtract the number of lines connecting i.e.

³C₂ = 3 pairs of men.  Thus for the case of 3 couples, the calculation is:

          3 x (2 x 3 – 2) – ³C₂ = 12 – 3 = 9

We verify by counting from the diagram that this is correct.

For 13 couples, we have

          13 x (2 x 13 – 2) – ¹³C₂ = 247 ways.

         

FYI, the general formula is

          n x (2n – 2) – ⁿC₂

JCCDQBHWHCB019 Combinatorics : Circular Permutations

Suggested Approach and Solution:-

     Draw a diagram.  Let’s assume that the special woman (W*) is at the 12 o’clock reference position.  [If not, we can always rotate our heads or rotate the table so that she is.] 

 

Together with the two lucky(?) men M₁ and M₂, they form one entity.  There are ³C₂ x 2!

= ³P₂ = 6 ways to choose and arrange these two men to sit besides this special woman.  The other 4 persons can arrange themselves relative to the reference entity in 4! = 24 ways (this is same as (5 – 1)! or ^5! / ₅).  Hence the number of ways = 6 x 24 = 144.

JCCDQBHWHCB011(i) Combinatorics : Uniform Over-counting (Division Principle)

     [ As an ice-breaker game, this is stupid!  Anyway … ]

Suggested Approach and Solution:-

     If the problem seems difficult, try a simpler problem first.  This is a useful heuristic / tactic, especially for permutation and combination problems.  Let’s say there are only six students.  Draw a diagram (a heuristic) with dots representing students, and arrows from each dot to other dots except the two dots beside it.  You will soon realize that each arrows goes in two directions.  This means there is over-counting by a factor of 2.  Whatever answer you get by counting the arrows forward must be divided by 2.

 

How many arrows are there?  (Heuristic: Think of an equivalent problem).  For each of the 6 dots, there are 6 – 3 = 3 arrows coming out (minus 3 because excluding itself and two beside it).

So the number of arrows is 6 x (6 – 3) = 18.  But we don’t really care about the direction of the arrows.  Because of the double-counting (and this is uniformly true for every pair of arrows), we must now divide this answer by 2 to get 9.  We can verify by counting from the diagram that this answer is correct.

Another approach: there are ⁶C₂ = 15 possible line segments (connections between two dots).  But we don’t count those on the perimeter of the hexagon, so we subtract 6 (because there are six sides all round the hexagon).  This gives 15 – 6 = 9.

For 17 students, the answer is: 17 x (17 – 3) / 2 = 119