Skip to content

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.]

2 Comments Leave one →
  1. Brian Gladman permalink

    Here an analytic solution:

    The filled in grid is shown above. Only the outer S’s can start and end the palindrome since the other S’s don’t have adjacent E’s.

    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.

    As discussed earlier we have to square this result to find the number of paths for the full palindrome, giving a total of 1,073,479,696 paths.

  2. I’ve posted my program and analysis here [ ] if you want to see it.

Leave a Reply

Note: HTML is allowed. Your email address will not be published.

Subscribe to this comment feed via RSS