跳到主要内容
← 返回题库
免费概率中等

Even Marbles Everywhere I

考察公司CitadelTwo Sigma

题目

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?

解析

先自己试一试,卡住了再打开提示。

提示 1

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

提示 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?

查看解析

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.