Even Marbles Everywhere I
Question
Each square of an board gets a marble, black or white, each with probability 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 block freely. Is the rest of the board then forced?
Hint 2
The last square of each of the first rows is forced. So is the last square of each of the first columns. What about the bottom-right corner?
Show solution
Count the good boards. There are boards in total, all equally likely. We show that the good boards correspond exactly to the ways of filling the top-left block.
Step 1: Fill the block any way you like.
Step 2: Finish the first rows. In each of rows –, the last square (column ) is forced: white if the row has an odd number of whites so far, black if even.
Step 3: Finish the first columns. In the same way, the bottom square of each of columns – is forced.
Step 4: The corner. Only the bottom-right square is left, and it must fix both row and column at once. That works only if row and column currently have the same parity. They do:
- Column so far has one forced square per row –, 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 block.
- Row so far has one forced square per column –, 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 block extends to exactly one good board, and every good board comes from its own top-left block. There are good boards.
Probability.
Answer: .