Predictable Board Game - A possible New Problem
Back to General discussions forum
The following is a draft problem description:
Two friends invented a new board game. They used a board which was a large grid of squares. The bottom left square on the board is the origin of the grid, having coordinates (0,0). Other squares on the board can be described by the usual (x,y) coordinates. The values of x and y can be 0 or any positive integer up to a maximum of 100,000.
A disc is placed on one square of the board and the friends take it in turns to move the disc. The first player to move the disc to the origin wins the game. The friends decided to allow three different kinds of move.
A move to the left decreases the x value of the position of the disc. Any size move is allowed provided that the disc remains on the board.
A move downwards decreases the y value of the position of the disc. Any size move is allowed provided that the disc remains on the board.
A diagonal move decreases both the x and y values of the position of the disc BY THE SAME AMOUNT. Any size move is allowed provided that the disc remains on the board.
Note that it is not possible for either the x or the y value of the disc position to increase.
For example, from the square (3,4) it is possible to move directly to any of the squares (2,4), (1,4), (0,4), (3,3), (3,2), (3,1), (3,0), (2,3), (1,2) and (0,1).
To make the game fair one player would place the disc on the board and the other player would get the first move. The two friends were pleased with their invention and enjoyed playing many games until they began to suspect that the game outcome is determined by the starting position of the disc; assuming optimal play.
We can describe some squares as winning squares (W) because the player making the first move is guaranteed to win the game, no matter what sequence of moves is played by their opponent; provided that the first player plays optimally.
Similarly we can describe squares as losing squares (L) because the first player is guaranteed to lose the game, no matter what sequence of moves they play, provided that their opponent plays optimally.
When squares are close to the origin it is easy to classify them. (8,8) is clearly a winning square because we can reach the origin in a single move. (1,2) is a losing square. The only valid moves from this square go to (0,2), (1,1), (1,0) or (0,1). From any of these positions the second player can make a move to the origin and win the game.
As positions get further from the origin it becomes harder to decide whether they are winning or losing positions. That is the object of this puzzle. The first line of the input data will contain a single integer N. N lines will follow. On each line there will be a pair of integers (separated by a space). These are the (x,y) coordinates of the disc position. For each position answer W or L to indicate winning or losing. Give all answers on a single line, separated by single spaces.
Example:
input:
14
1 2
8 8
45 73
57 32
162 100
353 216
645 1039
1262 2043
3062 4955
4303 6961
11181 6914
12537 7748
42312 26150
90853 56153
answer:
L W L W L W W W L W W L L W
Dear Clive, Hi!
Thanks a lot, I'll try to add it immediately since seemingly no-one has anything to add / object :)
Very curious where this puzzle originates from. I had sudden "deja vu" - in my childhood I seen such a puzzle / game described in one old soviet book (perhaps from 1956):
"Tzianshitzi is a Chinese national game, it translates as stones picking. Here are two heaps of stones and players in turn can take any number of stones from any of the heaps - or from both at once, but only equal amount. The one who takes last stone wins."
If I'm not greatly mistaken it is the same game.
I really wonder whether such game exists. Couldn't find anything about it at once :) Though for the puzzle it doesn't matter of course!