Four years ago, when I was in Grade 6 and in the Hanoi team training for the International Math Tournament of the Towns (IMTT), the leader of the Vietnam IMO team came and first provided me with an insight of what I now call game-theory.
He gave us the following problem:
Let there be 30 balls on the board, now two students come up and play. Each turn, they can only pick $1,4$, or $6$ balls. Provided that the last player to make a move wins. Then who has a strategy to win?
Now the solution to that problem is not difficult, I suppose, for those who read this, and I leave here a glimpse to the answer.
The person who picks the 30th ball wins, so we write $30W$, the player who picks the 29th ball, therefore, obviously loses, so we write $29L$. Continue with this logic, we have the following sequence: $30W, 29L,28W,27L,26L,25W,24L,....$ and we traces back to $1,4,6$, which helps us to determine the first person move.
A few months later, I came to the TIMC 2016, which is an elementary mathematics contest in Thailand. The following problem is proposed by Vietnam Delegation, and eventually appeared in the Team Contest, problem number 3
The problem indeed has an answer, illustrated below:
I shall now combine the two problems, which results in the following question I found quite interesting in solution.
Given a chessboard of size $8\times 8$. Two players are playing the following game:
- They take turn filling in numbers in the board. The numbers must be from $1$ to $64$.
- The first person can start anywhere on the board, filling any number he wanted
- Each person, there after, have to choose a square adjacent to the most recently filled square, and fill in a number that have a difference of 1,4,6 with one of the previously filled adjacent square (sharing an edge) of the chosen square.
- The number can go up or down (which means if you already have $12$, then you can fill in $6$ or $18$ is both okay) and they must not be repeated
The person who cannot make another move loses the game
Which one of the two players have the winning strategy?