Question
Introduction
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 casebycase analysis. I suspected that there is a short cut that
avoids casebycase 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 ^{5}C_{4} = 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 = ^{5}C_{4}
= 5.
(ii) Number of ways = 5 × 4
= 20.
(iii)
Pattern

Working

Number

{XXXX}

^{5}C_{1}
[5 columns, choose 1]

5

{XXXY}

done in part (ii)

20

{XXYY}

^{5}C_{2}
[5 columns, choose 2]

10

{XXYZ}

5 × ^{4}C_{2}
[5 ways for X, ^{4}C_{2}
ways for YZ]

30

{XYZW}

done in part (i)

5

Total
=

70

Number of ways = 5 + 20 + 10 + 30 + 5 = 70
Remarks
Don’t you hate casebycase 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 ballsandbins configuration can thus be
codified as a string of consisting of 4 grey dots (representing 4 grey balls) and
4 separators.
Because of this onetoone 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 ^{8}C_{4} , which is 70.
Shortcut for part (iii)
Number of ways = ^{4+4}C_{4}
= 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