**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. “**”) is***n*choose*r*
For example, if you have 8 different
balls and you want to choose 3 out
of the 8, the number of combinations is

^{8}C_{3}= 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,

*C*^{n}*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*_{r}**symmetrical property**. For example,^{8}C_{5}=^{8}C_{3}= 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^{8}C_{5}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*=^{9}C_{4}=^{9}C_{4}= 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*)
=

^{3}C_{1}´^{6}C_{3}= 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*)
=

^{6}C_{2}´^{3}C_{2}= 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*)
=

^{3}C_{1}´^{3}C_{1}´^{3}C_{2}= 3 ´ 3 ´ 3 = 27
The paths from

*A*to*P*are chosen**from the paths from***independently**P*to*B*. That is why we are able to multiply the numbers. Likewise, the other multiplications are justified because of**. Putting everything together,***independence*
# 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**

* IB Mathematics HL / SL (“Counting Principles”)

* Primary School Mathematics Olympiad

* anyone, young or old, who is interested in thinking

## No comments:

## Post a Comment