Question
Introduction
This is an
mathematics olympiad question for primary schools, and it is also a good
mind-stretching exercise for students taking H2 Mathematics or IB Mathematics. The problem can be solved using good tactics
(heuristics) and some knowledge of combinations. The number of ways to choose r objects out of n (a.k.a. “n choose r”) is
For example, if you have 8 different
balls and you want to choose 3 out
of the 8, the number of combinations is 8C3 = 56. You write 8 on top and 3 below and then introduce
new factors by successively decreasing each number by one, until the bottom factor
reaches 1. Notice that the number of
factors in the numerator is equal to the number of factors in the denominator.
Sometimes, nCr is written like a
2 by 1 column vector. Many teachers introduce the concept with a
formula using factorials, but the above formula is more practical
for calculations. Combinations have a nice
symmetrical property. For example, 8C5 = 8C3
= 56. Why? That is because choosing 5
objects out of 8 is the same as choosing 3 to
be rejected. This can be verified by
writing 8C5 out in full and cancelling the factors.
Solution
First, let
us note that every path from A to
B is equivalent to a sequence of
right arrows (®) and up arrows (á). In the above example, the
path corresponds to a sequence “®áᮮᮮá”. There
are 9
symbols in each sequence, of which
5 must be “go right” and 4 must
be “go forward”. [H12* Think of a related problem] The number of such paths is
W = # of paths from A to B = 9C4 = 9C4 = 126.
W = # of paths from A to B = 9C4 = 9C4 = 126.
However, we do not want the paths that pass
through P or Q. So we need to consider
X = # of paths from A to B
passing through P
Y = # of paths from A to B
passing through Q
The problem is, if you added these, the paths that
pass through P and Q would have been
double-counted. So we also need to
consider
Z = # of paths from A to B
passing through P
and Q
The required number of paths would be W –
(X + Y – Z) = W – X
– Y + Z. Let us calculate part by
part.
X
= # of paths from A to B passing through P
=
(# of paths from A to P) ´ (# of paths from
P to B)
= 3C1
´ 6C3 = 3 ´ 20 = 60
Y = # of paths from A to B
passing through Q
=
(# of paths from A to Q) ´ (# of paths from
Q to B)
= 6C2
´ 3C2 = 15 ´ 3 = 45
Z = # of paths from A to B
passing through P
and Q
=
(# paths A to P) ´ (# paths P
to Q) ´ (# paths Q to B)
= 3C1
´ 3C1
´ 3C2 = 3 ´ 3 ´ 3 = 27
The paths from A
to P are chosen independently
from the paths from P to B. That is why we are able to multiply the
numbers. Likewise, the other
multiplications are justified because of independence. Putting everything together,
# of paths from A
to B passing through
neither P nor Q
= W – X
– Y + Z = 126 – 60 – 45 + 27 = 48 J
H02. Use a
diagram / model
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
* GCE ‘A’ Level H2 Mathematics
(“Permutations and Combinations”)* IB Mathematics HL / SL (“Counting Principles”)
* Primary School Mathematics Olympiad
* anyone, young or old, who is interested in thinking
