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₂

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