Suppose you have a \(3 \times 3\) grid of squares. Each square can be green or red. The game is won if

• Each column has an odd number of red squares.
• Each row has an even number of red squares.

This game cannot be won! If you count the number of red squares in column \(i\) to be \(c_{i}\), then the total number of red squares on the board is

Since this is the sum of three odd numbers, \(N\) will be an odd number. However, you can count the total number of red squares on the board by adding all the numbers of red squares in each column:

Since this is the sum of three even numbers, \(N\) will be an even number.

Now consider a different game. A referee Rosa sends two randomly chosen integers \(a\) and \(b\) to Alice and Barbara, such that

They each in return provide a coloring:

• Alice provides a coloring for the \(a\)-th row, with an even number of red squares.
• Barbara provides a coloring for the \(b\)-th column, with an odd number of red squares.

They can win this game if the two colorings agree in their overlap.

Alice can choose four kinds of sequences: GGG, GRR, RGR, RRG. Barbara can choose four kinds of sequences: RRR, RGG, GRG, GGR. They each take an input that can take three values. The total number of deterministic strategies is found by counting how many ways to map a set with three items to a set with four items. That is,

You can encode each of these strategies as a three character sequence \(X_{0}X_{1}X_{2}\) where each character can be \(0\), \(1\), \(2\), or \(3\). The value of \(X_{0}\) dictates what to choose if \(a = 0\).

Here is some Python code. You import some packages:

from itertools import product

import numpy as np
np.random.seed(0)

You define some variables that contain the options for Rosa, Alice, and Barbara:

rosa_option = np.arange(3)

alice_option = [
    [False, False, False],
    [False, True, True],
    [True, False, True],
    [True, True, False],
]

alice_option = np.array(alice_option)

barbara_option = [
    [True, True, True],
    [True, False, False],
    [False, True, False],
    [False, False, True],
]

barbara_option = np.array(barbara_option)

You generate the random choices by Rosa for Alice and Barbara:

N = 16000

a = np.random.choice(rosa_option, size=N)
b = np.random.choice(rosa_option, size=N)

You define some functions for playing the games:

def deterministic(i, strategy, option):
    return option[strategy[i]]

def fraction_of_wins(a, b, f, g, a_option, b_option, N):
    x = deterministic(a, f, a_option)
    y = deterministic(b, g, b_option)

    n = np.arange(N)

    wins = np.equal(x[n, b], y[n, a])

    return np.sum(wins) / N

Here is some code for printing the results:

strategy = np.array([p for p in product((0, 1, 2, 3), repeat=3)])

M = 64

p = np.zeros((M, M), dtype=float)

for i in range(M):
    for j in range(M):
        p[i, j] = fraction_of_wins(strategy[i], strategy[j], N)

print(p[p > 0.8])

Upon inspection of the result, you can see that there are some combination of strategies that result in a probability of winning close to 8/9 (almost 89%).