**From New Scientist #2384, 1st March 2003** [link]

The entrants for the marathon formed a long line. They were told to number themselves from 1 upwards using the large stock of sticky-backed digits. This went well until it got to me. My number was an even three-figure perfect square.

The next person added one to my number, collected up the appropriate digits, but then stuck them on his back in the wrong order. The next person added one to that incorrect three-figure number, collected up the appropriate digits, but then stuck them on his back in the wrong order. The next person added one to that incorrect three-figure number, collected up the appropriate digits, but then stuck them on his back in the wrong order, and so on, and so on, and so on. The funny thing was that every third runner after me had a number which was a perfect square.

I only realised that something was wrong when, during the race, I overtook a runner with the same number as mine.

What was that number?

[enigma1228]

### Like this:

Like Loading...

This Python 3 program runs in 60ms.

Solution:The number was 256.The only possible sequences that start with an even 3-digit square, and then repeat that square later on are:

The numbers in brackets are those that are not required to be squares, and, indeed, none of them are squares.

In fact, none of the candidate chains of four numbers that both start and end with a square contain a square in the intermediate positions, so we can just consider transitions between squares. The graph of all such transitions between squares looks like this:

Even squares are shown in red, as are transitions that form a cycle in the graph.

We can see that the only path through the graph starting at an even square and including that square more than once is to start at 256 and go around the cycle of red arrows as many times as you like. It is possible to end the path by exiting the cycle and finishing on the edge to 625 with the last three runners to take numbers. (If there are a suitable number of runners involved (i.e. three, four or five remaining when we get to 361)). If we arrive at a node with only one or two runners remaining to allocate numbers to, we can exit that node without worrying that we need to subsequently allocate a square number.