Difference between revisions of "1993 IMO Problems/Problem 3"
(→Solution) |
|||
| Line 5: | Line 5: | ||
This is a very beautifully done video solution: https://www.youtube.com/watch?v=eAROaUpkgRo | This is a very beautifully done video solution: https://www.youtube.com/watch?v=eAROaUpkgRo | ||
| − | |||
== Solution == | == Solution == | ||
| − | + | The solution as described in the video is that all values of <math>n</math> are valid except when <math>n</math> 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 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. | |
[[File:IMO1993_P3_n1r.gif]] | [[File:IMO1993_P3_n1r.gif]] | ||
| Line 20: | Line 19: | ||
[[File:IMO1993_P3_n4r.gif]] | [[File:IMO1993_P3_n4r.gif]] | ||
[[File:IMO1993_P3_n5r.gif]] | [[File:IMO1993_P3_n5r.gif]] | ||
| + | |||
| + | [[File:IMO1993_P3_Label_n1.png]] | ||
| + | [[File:IMO1993_P3_Label_n2.png]] | ||
| + | [[File:IMO1993_P3_Label_n3.png]] | ||
| + | [[File:IMO1993_P3_Label_n4.png]] | ||
| + | [[File:IMO1993_P3_Label_n5.png]] | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
[[File:IMO1993_P3_n6r.gif]] | [[File:IMO1993_P3_n6r.gif]] | ||
| Line 34: | Line 34: | ||
[[File:IMO1993_P3_n10r.gif]] | [[File:IMO1993_P3_n10r.gif]] | ||
| + | [[File:IMO1993_P3_Label_n6.png]] | ||
| + | [[File:IMO1993_P3_Label_n7.png]] | ||
| + | [[File:IMO1993_P3_Label_n8.png]] | ||
| + | [[File:IMO1993_P3_Label_n9.png]] | ||
| + | [[File:IMO1993_P3_Label_n10.png]] | ||
| + | |||
| + | ~ Tomas Diaz. orders@tomasdiaz.com | ||
Revision as of 18:31, 21 November 2023
Contents
Problem
On an infinite chessboard, a game is played as follows. At the start, 
pieces are arranged on the chessboard in an 
by 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 for which the game can end with only one piece remaining on the board.
Video Solution
This is a very beautifully done video solution: https://www.youtube.com/watch?v=eAROaUpkgRo
Solution
The solution as described in the video is that all values of are valid except when 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 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.
~ Tomas Diaz. orders@tomasdiaz.com
This problem needs a solution. If you have a solution for it, please help us out by adding it.
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 | ||
