Henry Ernest Dudeney/Modern Puzzles/160 - Going to Church/Solution

Modern Puzzles by Henry Ernest Dudeney: $160$

Going to Church

A man living in the house shown as $H$ in the diagram wants to know what is the greatest number of different routes by which he can go to the church at $C$.

The possible roads are indicated by the lines, and he always walks either due $N$, due $E$, or $N.E.$;

that is, he goes so that every step brings him nearer to the church.

Can you count the total number of different routes from which he may select?

Solution

$321$ different routes.

Proof

Starting from $H$, there is one way to get to each of the points in the northerly direction, and one way to those due east.

Taking the second column, there are as many ways to get to each point as the sum of those to each of the points from which you can reach that point directly.

That is, let $R_{m, n}$ be the number of routes to the point in row $m$ and column $n$.

Then:

$R_{m, n} = R_{m - 1, n} + R_{m, n - 1} + R_{m - 1, n - 1}$

on the understanding that if $n - 1$ or $m - 1$ is outside the grid, its contribution is $0$.

Hence we can build an array of the number of routes, where each number is $R_{m, n}$ as defined:

$\begin{array}{ccccc} 1 & 9 & 41 & 129 & 321 \\ 1 & 7 & 25 & 63 & 129 \\ 1 & 5 & 13 & 25 & 41 \\ 1 & 3 & 5 & 7 & 9 \\ 1 & 1 & 1 & 1 & 1 \end{array}$

and the result follows.

Also see

• Definition:Pascal's Triangle, which is what you get if you can't go diagonally.

Sources

• 1926: Henry Ernest Dudeney: Modern Puzzles ... (previous) ... (next): Solutions: $160$. -- Going to Church
• 1968: Henry Ernest Dudeney: 536 Puzzles & Curious Problems ... (previous) ... (next): Answers: $417$. Going to Church