The Computer Laboratory

Practice Paper 1 Question 13

On a grid of \(m\times n\) squares, how many ways exist to get from the top-left corner to the bottom-right corner if you can only move right or down on an edge?

The above links are provided as is. They are not affiliated with the Climb Foundation unless otherwise specified.

Warm-up Questions

  1. 16 tennis players participate in a doubles tournament and are paired at random. How many ways are there to select a pair?

  2. How many different ways can a football team's manager choose 5 penalty takers from 11 players?

Hints

  • Hint 1
    How many steps in total must be taken?
  • Hint 2
    From a total of \(m+n\) steps, how many are rightward steps and how many are downward steps?
  • Hint 3
    If we have \(m\) rightward steps, how many combinations of them are there?
  • Hint 4
    For each combination of rightward steps, how many combinations of downward steps are there?

Solution

Regardless of the path taken, you must travel \(m\) steps right and \(n\) steps down, i.e. you must always travel \(m+n\) steps. Of these, we consider the number of different ways we may choose \(m\) to be rightward steps. This is \(\binom{m+n}{m}=\frac{(m+n)!}{n!m!}\). For each of these combinations, the remaining \(n\) steps down are uniquely determined i.e. there is only 1 combination since \(\binom{m+n-m}{n} = \binom{n}{n} = 1\), so \(\binom{m+n}{m}\) is our final answer.

Similarly, we may first find the combinations of \(n\) downward steps and fix rightward steps to obtain \(\binom{m+n}{n}\) as our answer.

Another way to look at this is to consider the permutations of \(m+n\) steps, where \(m\) rightward steps and \(n\) downward steps are both indistinguishable types of steps. We find the number of permutations for \(m+n\) things, and remove (by dividing by) the number of permutations specifically for just the rightwards and downward steps. This gives us the answer \(\frac{(m+n)!}{m! \cdot n!}\).

If you have queries or suggestions about the content on this page or the CSAT Practice Platform then you can write to us at oi.footasc@sulp.ecitcarp. Please do not write to this address regarding general admissions or course queries.