# Sunday Times Teaser 2935 – A Palindrome

### by Graham Smithers

#### Published December 23 2018 (link)

In this Teaser, a jig* is defined as an outwards move to an adjacent empty square, either horizontally, upwards or downwards, the letter * being inserted in all such squares.

Begin with the letter W on a regular grid of empty squares.

From the W, jigO. From every O, jigN. From every N, jigD, and so on until the central diagonal reads SELIM’S TIRED, NO WONDER, IT’S MILES.

Looking at your grid of letters, in how many ways can you trace the palindrome above?

[You can start at any S, move to adjacent letters till you reach the W and then on to any S (including the one you started at). You may move up and down, left and right.]

Instead of counting the paths for the complete palindrome, we can simplify the teaser by considering only paths from the central W to the outer S’s.  If there are $$N$$ such paths, we can then form the full palindrome by combining each of these paths with the $$N$$ reverse paths back to the outer S’s, giving $$N^2$$ paths in total.
Since the grid is is horizontally and vertically symmetric, we can further simplify the analysis by only considering its upper left quadrant.  At each of the 13 steps from the central W to the outer S’s in this quadrant we can choose to move either up or left, which means that there are $$2^{13}$$ paths in total.  And since there are four quadrants, there are a total of $$4.2^{13}$$ paths in the full grid.  But the two horizontal and two vertical paths have been counted twice (since they are each in two quadrants) so we have to reduce the count by 4, giving $$4(2^{13} – 1)$$ paths in total – 32764 paths.