Sunday, November 8, 2015

[H2_ACJC2015P2Q7] Choosing balls by another method


     This question is taken from a Junior College examination in Singapore.  It looks deceptively simple.  Actually, there is an easy way to solve it.  But reading the question made me do a double take.  Since we are choosing a maximum of  4  balls for a given colour and balls of the same colour are indistinguishable, why bother having  6  balls?  It turns out that as long as we have  4  balls or more for each colour, the number of balls would not matter.  So this issue is a distractor.
     I shall explain my standard approach to solving this type of problem.  I present a solution in which part (iii) is solved via a case-by-case analysis.  I suspected that there is a short cut that avoids case-by-case analysis and I finally found a short cut by a flash of inspiration.  So I shall also present the short cut to part (iii).

My Approach
     When there are repeated indistinguishable objects, I imagine objects of the same type being stacked up in columns.  For part (i) of our problem, see the diagram on the left.  I am just choosing  4  columns out of  5  (indicated by the up arrows).  Once I have chosen the columns, I just take one ball out from each column and put it into my selection.  Imagine putting them into a plastic bag – the order of the balls does not matter.  The number of ways to do this is  5C4 = 5.

For part (ii), see the diagram on the right.  First I choose one of the 5 columns and automatically take three balls (it does not matter which three actually) from that column.  From the remaining 4 columns, I choose one and pick out one of the balls from that column.  I can do this in  5 × 4 = 20 ways.  I call the pattern in part (i) “{XYZW}” (all different colours) and the pattern in part (ii) “{XXXY}” (three of one colour and another one of a different colour).  The curly brackets are a reminder that the order does not matter.   For part (iii), we can work out the other patterns and total up the number of ways.

Solution 1

(i)    Number of ways = 5C4 = 5.

(ii)   Number of ways = 5 × 4 = 20.

5C1  [5 columns, choose 1]
done in part (ii)
5C2  [5 columns, choose 2]
5 × 4C2  [5 ways for X, 4C2 ways for YZ]
done in part (i)

Total =
             Number of ways = 5 + 20 + 10 + 30 + 5 = 70

     Don’t you hate case-by-case analysis?  After thinking for a while, I found a short cut.  This requires thinking of a related problem.  Let us say, for example, we choose  2  orange balls,  1  green ball and  1  blue ball.  This is equivalent to throwing  4  grey (AmE. gray) balls with  2  of them going into a bin for marked “orange”,  1  into a bin marked “green”  and  1  into a bin marked “blue”.  There are  5  bins, one corresponding to each colour and they are separated by  4  grey separators (one less than the number of bins).  The number of grey balls in each bin indicates the number of balls of the respective colour chosen.  The aforementioned configuration can be codified as a string of symbols consisting of two dots followed by two separators, then a dot, a separator, a dot, and finally a separator.  Every balls-and-bins configuration can thus be codified as a string of consisting of 4 grey dots (representing 4 grey balls) and 4 separators. 

     Because of this one-to-one correspondence, the number of ways of choosing  4  coloured balls is exactly the same as the number of strings of symbols.  There are 8 symbols (4  dots and 4 separators).  Of the 8 positions for the symbols, we need to choose  4  to put in the dots.  The rest will, of course, be filled by separators.  That means  8C4 , which is  70.

Short-cut for part (iii)
     Number of ways = 4+4C4 = 70.

I hope you have learned something useful.   J

H02. Use a diagram / model
H03. Make a systematic list
H04. Look for pattern(s)
H08. Make suppositions
H09. Restate the problem in another way
H10. Simplify the problem
H11. Solve part of the problem
H12* Think of a related problem

Suitable Levels
* ‘A’ Level H2 Mathematics (» Grade 11 / 12)
* IB Mathematics SL and HL (Binomial coefficients, counting principles)
* other syllabuses that involve combinatorics (combinations and selections)
* whoever is interested

No comments:

Post a Comment