Game of Life is not fair

Define the following sets:
$A' = \{(0,1), (0,2), (1,2), (2,0), (2,1)\}$
$A = \{(x,y) \in \mathbb{N}_0 \times \mathbb{N}_0 \mid \exists (x', y') \in A', x \equiv x' \mod 3, y \equiv y' \mod 3 \}$
$B = \{(x,y) \in \mathbb{N}_0 \times \mathbb{N}_0 \mid (y,x) \notin A \}$

By observing the $5$ cases, we can see that the first player can always move from a point in $A$ to a point in $B$ . Also, the second player can't move from a point in $B$ to a point not in $A$ . So, if the starting state is in $A$ , the first player can always play in a way that puts the second player at a point in $B$ . Because $A$ does not contain one of the $2$ final losing states for the first player, and the sum of the coordinates of the point decrease all the time, the game will eventually end, and the first player can't lose.

The fact that all the other states are losing states for the first player follows from symmetry of the moves and the sets.

There are $500$ points $(x, y)$ in $A$ in the interval $[1, 30] \times [1, 30]$ .

We first observe that every coordinate can be written in the form [a,b], where a and b are the least residues of the coordinates modulo 3. ( ie. a,b= 0/1/2). For example, (8,9) would be written as [2,0]. We call a irreducible if it cannot be changed to another least residue modulo three without resulting in either the x or y coordinate being turned into a negative number. For an instance, (0,6) when written as [0,0], the first zero in [0,0] would be irreducible, while the second one isn't. We claim that all coordinates pair in the form [0,1], [1,2], [2,0], [0,2], [2,1] are the winning positions while [2-2], [0,0], [1,1], [1,0] are the losing ones for player A.

Note: (a,b) will still denote the actual coordinates.

PROOF: note that for the case [0,1], during the first move, the first player only needs to move the token one unit down, resulting in a new position in the form [0,0]. If both the x and y coordinates are irreducible for player B, then we are done. If any ( or both) of the coordinates are reducible , note that after player B made his move we can always move the token back to a [0,0] position. What player A needs to do is merely mimic the previous move of player B ie. If player B moves the token 1 unit left, then player a should also move the token to the left, but by 2 units. Since the total number of units moved after both players complete their moves would be 3, this obviously results in a [0,0] coordinate. Eventually since there are only finite number of units both players can move, player A's last move will eventually end up on (0,0), leaving player B out of valid moves.

For the case [1,2], during his first move, player A should move the token one unit down, turning the coordinates into a [1,1] type. Whatever move player B performs, we can always turn the coordinates back into a [1,1] type again or even better, into a [0,0] type coordinates which practically gurantees us a win. To show why this is true, let's us consider all possible moves of player B. He can either move the token one unit left or two units down as long as the coordinates are reducible. If he chooses to move the token to the left, the coordinates will be in [0,1] form, what player A needs to do in the next turn is to merely shift the token 1 unit down, resulting in a [0,0] form coordinate. From our proof above, player A will always win from this point onwards if he adopts the right strategy. What if player B chooses to shift the token 2 units down? It will result in a new coordinate in the form [1,2], can adopt a symmetric strategy to move the token one unot down as well, resulting in a [1,1] type coordinate. Eventually the y coordinate will become irreducible after some number of moves and player B would be forced to move the token one unit left to a [0,1] position, and player A will clench the win by moving the token one unit down to a [0,0] type coordinate.

If the initial position is of the type [2,0], during his first move, player A should move the token two units to the left resulting in a [0,0] type new position, and a win eventually. ( see above ).

If the initial position is of the type [0,2], player A should first move the token one unit down to a [0,1] position. We will show that as long as player B is able to come up with a valid move, we will always be able to move the token to a new [0,1] position. To prove this, let's consider all possible moves of player B. If he chooses to move the token one unit to the left, the new position will be of [2,1] type, player A only needs to mimic player's B move to move it two units to the left, resulting in a [0,1] type coordinates. If he chooses to move the token 2 units down instead, player A should apply the symmetric strategy as well to move the token to a new [0,1] position. Eventually, after one of player's A moves, he will land the token on the actual coordinates (0,1), leaving player B out of moves.

For the case [2,1], in his first move, player one should move the token two units to the left, resulting in a [0,1] position. The rest of the proof follows from the case above.

Now, we proceed to prove that the cases [0,0], [1,1], [1,0] and [2,2] are the losing starting positions for player A. We ( of course) make the assumption that player B, like player A knows the strategy of winning the game and will always strive to win the game.

If the starting position for player A is [0,0], we can show that whatever move player A performs, player B can always move the token back to a [0,0] position. We consider all possible moves player A can make. If he chooses to move the token two units to the left, player B can always mimic his move by moving the token one unit to the left, resulting in a [0,0] position again. The same principle applies if player A moves the token one unit down. Eventually, player B will land the token on (0,0) and player A loses as he is out of valid moves.

For the case [1,1], after player A made his move, the position of the token will either on the form [2,1] or [1,0]. For the first case, player B should move the token 1 unit to the left, resulting in another [1,1] position again. If player A places the token on the position of [1,0] type, what player B needs to do to secure his win is to move the token one unit to the left, resulting in a [0,0] position, and hence a win. ( as proven above). If player A didn't make the mistake of placing the token on a [1,0] position, eventually he will have to do so when the x coordinate of [1,0] becomes irreducible. So player B will win regardless.

For the case [1,0], note that after player A makes a move, the possible new positions must all be of the form [2,0] or [1,2]. For both cases, player B can always move the token to a new position of the form [1,0]. After a finite amount of moves, player B will eventually land the token on (1,0), and player A will lose the games as there's no valid moves left.

Finally, for the position [2,2], note that no matter how player A moves, the token will always land on position [0,2] or [2,1]. For both of these cases, player B can move the token such that it will land on positions [0,0] and [1,1] respectively, which we have proven to be the losing positions of player A. Hence player B wins.

After proving all the cases, a quick computation reveals that there are (5)(10)(10)=500 such winning positions for player A. Note that we use the observation that there are 10 numbers from 1-30 which are congruent to 0 mod 3, 10 numbers which are congruent to 1 mod 3 and 10 numbers which are congruent to 2 mod 3.

Examining the small cases, we can easily form the following theory:

If it is the first player's turn to move, the position is winning for her iff $(x \bmod 3,y\bmod 3) \in \{ (0,1), (0,2), (1,2), (2,0), (2,1) \}$ .

If it is the second player's turn to move, the position is winning for him iff $(x \bmod 3,y\bmod 3) \in \{ (0,2), (1,0), (1,2), (2,0), (2,1) \}$ .

This is then easily proved by induction: for each position $(x\bmod 3, y\bmod 3,\text{current player})$ we examine the possible moves and show that:

1. Each move from a losing position leads to a winning position for the other player.
2. For each winning position there is a move that leads to a losing position for the other player.

The set of starting positions can be divided into 100 "squares" such that each contains each combination $(x\bmod 3,y\bmod 3)$ exactly once. And as 5 of 9 such positions are winning for the first player, the answer is $5 \times 100 = \fbox{500}$ .

Player 1's (PL1's) strategy is to lead PL2 to those points, where any next step of PL2 will make him/her lose. There are two such points: (0, 0) and (0, 1). Remember, that the token should cross any axis for the player to lose.

PL1 can keep the token on same diagonal till it comes close to an axis. For example, if PL2 goes 2 points down, PL1 can move it 2 points left; if PL2 goes 1 point left, PL1 can move it 1 point down.

This lets us to define a pattern of points on the plane, such that if PL2 has his/her turn there, PL1 will win anyway - the "winning" points. This pattern is periodic with size of $3 \times 3$ only.

Then we need to find the pattern of starting points, from which PL1 can reach with 1 step any of the "winning" points. This pattern is also $3 \times 3$ containing 5 such points. $30 \times 30$ area contains exactly 100 such patterns with total 500 points.

2 possibilidades de ficha, 3 turnos, 30 posições 900 possibilidades no total, então posições = raiz de possibilidades, 2/3 das possibilidades no total de turnos, então é 2/3 das posições, 2/3 de 30 = 20, 20² = possibildades, possibilidades = 400, diferença de possibilidades = resultado das diferenças das posições = 900-400=500 possibilidades