Charlotte's coin vs MATH board
Charlotte places a coin on the center square marked in the seven by seven grid shown below.
How many ways are there for her to spell by moving to three other squares if for each move she can move the coin to either a square with a common side or a diagonally adjacent square?
The answer is 104.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
1 solution
We need to count all paths of length 4 beginning in the centre ("M") and ending on the edge (an "H"). To keep track of the number of paths, we make a copy of the grid, and label each cell with the number of paths that end in it (so we solve the problem for the words "MA", then "MAT", then "MATH"). This table is easily generated; every "A" has exactly one path ending in it, and moving outwards, we just sum the adjacent cells from the previous iteration:
The answer is the sum of the "H" cells, highlighted in green, or 1 0 4
The generation of new terms by summing previous adjacent terms is very similar to the rule for generating Pascal's triangle, and in fact the rows (or columns) of the square grid correspond to this variant: Trinomial triangle , which gives a quick way of solving the generalisation of this problem to longer words (MATHEMATICS has 2 3 6 1 9 2 paths!)
(by the way, I thought this was a nicely balanced problem - large enough to not be completely trivial, but small enough to allow several different approaches)