Skip to content
← Back to all questions
FreeProbabilityMedium

Even Marbles Everywhere I

Asked atCitadelTwo Sigma

Question

Each square of an 8×88 \times 8 board gets a marble, black or white, each with probability 12\tfrac12 independently. What is the probability that every row and every column contains an even number of white marbles?

Solution

Try it yourself first. Open a hint if you get stuck.

Hint 1

Fill the top-left 7×77 \times 7 block freely. Is the rest of the board then forced?

Hint 2

The last square of each of the first 77 rows is forced. So is the last square of each of the first 77 columns. What about the bottom-right corner?

Show solution

Count the good boards. There are 2642^{64} boards in total, all equally likely. We show that the good boards correspond exactly to the 2492^{49} ways of filling the top-left 7×77 \times 7 block.

Step 1: Fill the 7×77 \times 7 block any way you like.

Step 2: Finish the first 77 rows. In each of rows 11–77, the last square (column 88) is forced: white if the row has an odd number of whites so far, black if even.

Step 3: Finish the first 77 columns. In the same way, the bottom square of each of columns 11–77 is forced.

Step 4: The corner. Only the bottom-right square is left, and it must fix both row 88 and column 88 at once. That works only if row 88 and column 88 currently have the same parity. They do:

  • Column 88 so far has one forced square per row 11–77, each matching its row's parity in the block. So its number of whites has the same parity as the total number of whites in the 7×77 \times 7 block.
  • Row 88 so far has one forced square per column 11–77, so by the same argument it also matches the parity of the block's total.

Both have the same parity, so one choice of corner fixes both: white if both are odd, black if both are even.

So every 7×77 \times 7 block extends to exactly one good board, and every good board comes from its own top-left block. There are 2492^{49} good boards.

Probability.

P=249264=1215=132,768≈0.00003.P = \frac{2^{49}}{2^{64}} = \frac{1}{2^{15}} = \frac{1}{32{,}768} \approx 0.00003.

Answer: 0.000030.00003.