Consider two arbitrary progressively bounded combinatorial games G_1 and G_2 wit
ID: 3111629 • Letter: C
Question
Consider two arbitrary progressively bounded combinatorial games G_1 and G_2 with positions x_1 and x_2. If for any third such game G_3 and position x_3, the outcome of (x_1, x_3) in G_1 + G_3 (i.e., whether it's an N- or P-position) is the same as the outcome of (x_2, x_3) in G_2 + G_3, then we say that the game-position pairs (G_1, x_1) and (G_2, x_2) are equivalent. Prove that equivalence for game-position pairs is transitive, reflexive, and symmetric. (Thus, it is indeed an equivalence relation.)Explanation / Answer
Transitive:
Let the game position (G1, x1) equivalent to the game position (G2, x2). Also, the game position (G2, x2) equivalent to the game position (G3, x3).
So, we must have that the outcome of (x1, x3) is equivalent to the outcome of (x2, x3). And, the outcome of (x2, x3) is equivalent to the outcome of (x3, x3).
This implies that the outcome of (x1, x3) is equivalent to the outcome (x3, x3).
that means, the game position pairs (G1, x1) and (G3, x3) are equivalent.
Thus, the equivalent game position paris (G1, x1) and (G2, x2) and equivalent game position paris (G2, x2) and (G3, x3), implies that the game position pairs (G1, x1) and (G3, x3) are equivalent.
Hence, the equivalence for the game position pairs is transitive.
Symmetric:
Let the game position (G1, x1) equivalent to the game position G2, x2).
Then we must have, that the outcome of (x1, x3) in G1+G3 is same as the outcome of (x2, x3) in G2+G3.
That means, the outcome of (x2, x3) in G2+G3 is same as the outcome of (x1, x3) in G1+G3.
So, the game position pairs (G2, x2) and (G1, x1) are equivalent.
Therefore, the equivalent game position pairs (G1, x2) and (G2, x1) implies that the game position pairs (G2, x2) and (G1, x1) are equivalent.
So, the equivalence of the game position pairs is symmetric.
Reflexive:
The outcome of the (x1, x3) in G1+G3 always equivalent to the outcome of (x1, x3) in G1+G3
So, the equivalnce game position pairs is reflexive.
Since, all the three properties of an equivalence relation are satisfied by the equivalnce for the game position pairs, we can say that the equivalnce for the game position pairs is an equivalence relation.