1993 IMO Problems/Problem 3

Problem

On an infinite chessboard, a game is played as follows. At the start, $n^2$ pieces are arranged on the chessboard in an $n$ by $n$ block of adjoining squares, one piece in each square. A move in the game is a jump in a horizontal or vertical direction over an adjacent occupied square to an unoccupied square immediately beyond. The piece which has been jumped over is removed. Find those values of $n$ for which the game can end with only one piece remaining on the board.

Video Solution

This is a very beautifully done video solution by YouTuber Mr. Math: https://www.youtube.com/watch?v=eAROaUpkgRo

Solution

The solution as described in the video is that all values of $n$ are valid except when $n$ is divisible by 3. He describes why those values are not valid using modular math and why the other ones are by creating an algorithmic pattern of reducing the matrices by taking out pieces in subarrays of 3 by m.

In the video he made a mistake when reducing the 5x5 to a 2x2 as someone pointed out in the comments on the video. I made sure my animated gif for when $n=5$ was correct.

I was going to write a solution to this but since Mr. Math in the video does a really beautiful solution of it I decided to write a code that will output these animated gifs with the cases for n=1 through 10 showing them whether they're valid or not depending on how many pieces are left. I used the algorithm described by Mr. Math in the video along and some recursive functions and some visualization functions. My code can generate the animation for any value of $n$ as long as there is enough memory for the file size and to handle the recursive function. I had to reduce the animated gif file sizes significantly. The original animated give for when $n=13$ was 30MB. I wrote the code in Matlab.

I don't know how to upload it to this page. If anyone wants the code, you can send me an email and I can gladly share it. Enjoy the animated gifs.

IMO1993 P3 Label n1.png IMO1993 P3 Label n2.png IMO1993 P3 Label n3.png IMO1993 P3 Label n4.png IMO1993 P3 Label n5.png

IMO1993 P3 n1r.gif IMO1993 P3 n2r.gif IMO1993 P3 n3r.gif IMO1993 P3 n4r.gif IMO1993 P3 n5r.gif


IMO1993 P3 Label n6.png IMO1993 P3 Label n7.png IMO1993 P3 Label n8.png IMO1993 P3 Label n9.png IMO1993 P3 Label n10.png

IMO1993 P3 n6r.gif IMO1993 P3 n7r.gif IMO1993 P3 n8r.gif IMO1993 P3 n9r.gif IMO1993 P3 n10r.gif


~ Tomas Diaz. orders@tomasdiaz.com

Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.

See Also

1993 IMO (Problems) • Resources
Preceded by
Problem 2
1 2 3 4 5 6 Followed by
Problem 4
All IMO Problems and Solutions