Hops And Slides But Never Square


A horizontal row comprising of $2n + 1$ squares has $n$ red counters placed at one end and $n$ blue counters at the other end, being separated by a single empty square in the centre. For example, when $n = 3$.

A counter can move from one square to the next (slide) or can jump over another counter (hop) as long as the square next to that counter is unoccupied.

Let $M(n)$ represent the minimum number of moves/actions to completely reverse the positions of the coloured counters; that is, move all the red counters to the right and all the blue counters to the left.

Prove that $M(n)$ can never be a perfect square.


When presented with problems like this it is always helpful to spend a short time "playing" with counters. This should reveal that a minimal approach would only involve "forward" actions; that is, red counters only moving to the right and blue counters only moving to the left. In order to move all the red counters to the right and the blue counters to the left it is clear that each of the red counters must hop over each of the blue counters (or vice versa). With the exception of the starting and finishing positions, two counters of the same colour should never appear next to each other, otherwise one of the counters would need to move "backwards" to make space for a counter of the other colour to hop over and this would undermine an optimal strategy.

Experimentally the following results can be obtained.


The results seem to suggest that the formula, $M(n) = n(n + 2) = n^2 + 2n$.

We shall prove this result by considering the total distance travelled by all of the counters. Note that a slide involves travelling a distance of one square whereas a hop accounts for a distance of two squares.

Once a complete reversal of positions has taken place each of the red counters will have moved a total distance of $n+1$ squares to the right and each blue counter will have moved $n + 1$ squares to the left. So the minimum distance that all of the counters travelled will be a distance of $2n(n+1)=2n^2+2n$ squares.

As explained above, during this process each counter of one colour must hop over every counter of the other colour once and only once. Therefore a total of $n \times n = n^2$ hops (actions) will take place, but as each hop moves a distance of two squares, the hops will account for $2n^2$ squares of the total distance travelled.

Therefore the slides will account for $2n^2 + 2n - 2n^2 = 2n$ squares of the total distance travelled, which also represents the total number of slides (actions).

Hence the total number of actions (made up of hops and slides) will be $n^2 + 2n$.

Therefore $M(n) = n^2 + 2n = (n^2 + 2n + 1) - 1 = (n + 1)^2 - 1$.

But as $n \ge 1$ and $M(n)$ is one less than a perfect square we prove that it can never be square itself.

With the exception of $M(2) = 8$, is it possible for $M(n)$ to be cube?
Given that there are $x$ red counters and $y$ blue counters find a formula for $M(x, y)$.

Problem ID: 372 (07 Aug 2010)     Difficulty: 3 Star

Only Show Problem