## Friday, April 10, 2015

### [OlymPri20150408CBP] Paths to avoid {#Combinatorics}

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.

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 + YZ) = WXY + 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
= WXY + 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”)