A marker is placed at the origin of an integer lattice. Calvin and Hobbes play the following game. Calvin starts the game and each of them takes turns alternatively. At each turn, one can choose two (not necessarily distinct) integers a and b, neither of which was chosen earlier by any player and move the marker by a units in the horizontal direction and b units in the vertical direction. Hobbes wins if the marker is back at the origin any time after the first turn. Determine whether Calvin can prevent Hobbes from winning.
Here Hobbes can return to the origin at any time by 'undoing' the displacements from the origin.
Suppose Calvin can moves include (a,b), followed by (-c,-d) by Hobbes and (e,f) by Calvin again . Then Hobbes can move back to the origin by (a+e-c, b+f-d).
We observe the following:
1) the Hobbes tries to move back towards origin while Calvin tries to move away.
2) none of the moves repeat that is a, e, c are all distinct and so are b, d, f
3) for every positive move that Calvin makes, there is a negative move that Hobbes can make which is distinct and non-repeating. Hence the origin is a P-Position. A P-position is one where the player who has just played can force a win. A position is called an N-position if the player whose turn it is can force a win and Hobbes uses it to his advantage. Therefore Calvin must find a P position other than the origin.
4) when the moves are strictly horizontal or strictly vertical, Hobbes cannot reset back to the origin because one of the co-ordinates is 0 and it will have to be repeated to get back to the P-position.
Therefore Calvin can find P-positions by either moving horizontally only or vertically only
For example, Calvin can move (1,0) in the first move and Hobbes is forced to move in the vertical direction, say (-1, -1), then Calvin can undo the vertical direction by flipping the marker to the opposite side with (2,-2) In other words Calvin forces two of the diagonals to be P-positions and maintains his moves to these diagonals with non-repeating numbers.
5) Since the numbers are incrementing by 1 and Calvin uses up both the positive and negative of the same integer, Calvin has a winning strategy.
6) the axes can be the players N positions since moving to the axes can let them use the diagonal.
7) once both players arrive at the diagonal they can remain on the diagonal by alternating
Here Hobbes can return to the origin at any time by 'undoing' the displacements from the origin.
Suppose Calvin can moves include (a,b), followed by (-c,-d) by Hobbes and (e,f) by Calvin again . Then Hobbes can move back to the origin by (a+e-c, b+f-d).
We observe the following:
1) the Hobbes tries to move back towards origin while Calvin tries to move away.
2) none of the moves repeat that is a, e, c are all distinct and so are b, d, f
3) for every positive move that Calvin makes, there is a negative move that Hobbes can make which is distinct and non-repeating. Hence the origin is a P-Position. A P-position is one where the player who has just played can force a win. A position is called an N-position if the player whose turn it is can force a win and Hobbes uses it to his advantage. Therefore Calvin must find a P position other than the origin.
4) when the moves are strictly horizontal or strictly vertical, Hobbes cannot reset back to the origin because one of the co-ordinates is 0 and it will have to be repeated to get back to the P-position.
Therefore Calvin can find P-positions by either moving horizontally only or vertically only
For example, Calvin can move (1,0) in the first move and Hobbes is forced to move in the vertical direction, say (-1, -1), then Calvin can undo the vertical direction by flipping the marker to the opposite side with (2,-2) In other words Calvin forces two of the diagonals to be P-positions and maintains his moves to these diagonals with non-repeating numbers.
5) Since the numbers are incrementing by 1 and Calvin uses up both the positive and negative of the same integer, Calvin has a winning strategy.
6) the axes can be the players N positions since moving to the axes can let them use the diagonal.
7) once both players arrive at the diagonal they can remain on the diagonal by alternating
No comments:
Post a Comment