返回题库

井字棋求和

Tic-Tac-Toe Sum

专题
Probability / 概率
难度
L4

题目详情

你面前有一个井字棋九宫格。将整数 1 到 9 均匀随机地排列到 9 个格子中。求每一行和每一列的和都为奇数的概率。

There is a tic-tac-toe grid in front of you. You permute the integers 1-9 to the 9 squares in the grid uniformly at random. Find the probability that the sum of each row and column is odd.

解析

3×33\times3 网格的每个格子编号,并只看其中数字的奇偶性: 若某格中的整数为奇数,则在该格放一个 11;若为偶数,则放一个 00。 因为 1,3,5,7,9 一共有五个奇数,而 2,4,6,8 一共有四个偶数,所以我们需要一个恰好含有五个 113×33\times3 二元矩阵。

题目要求每一行和每一列的和都为奇数,也就是说每一行和每一列都必须含有奇数个 11。对于一行(或一列)中的 3 个位置来说,奇数个 11 只能是 11 个或 33 个。由于总共有 5 个 11,所以每行的 11 的个数(每列也一样)必须是 (3,1,1)(3,1,1) 的某种排列。

因此,恰好有一行全为 11,也恰好有一列全为 11。一旦选定哪一行(3 种选择)和哪一列(3 种选择)是“全 1 行”和“全 1 列”,这个矩阵就唯一确定了:把选定的那一整行和那一整列都填成 11。因此,一共得到 3×3=93\times 3 = 9 个不同的奇偶性矩阵;每个矩阵都恰好有五个 11,并且每一行、每一列对模 2 都同余于 11

对于每个这样的奇偶模式,可以把五个奇数填入这五个位置,共有 5!5! 种方法;把四个偶数填入剩余四个位置,共有 4!4! 种方法。因此,有利的排列数为 95!4!.9\cdot 5!\cdot 4!. 而总排列数是 9!9!,所以所求概率为 95!4!9!=9(5!4!)9!=25920362880=114.\frac{9\cdot 5!\cdot 4!}{9!} = \frac{9\cdot (5!\,4!)}{9!} = \frac{25920}{362880} = \boxed{\frac{1}{14}}.


Original Explanation

Label the 3×33\times3 grid cells and view each placed integer by its parity: put a 11 in a cell if the integer there is odd and a 00 if it is even. There are five odd integers (1,3,5,7,9) and four even integers (2,4,6,8), so we need a 3×33\times3 binary matrix with exactly five 11's.

The requirement that each row and each column sum to an odd number means that each row and each column has an odd number of 11's. For a 33-entry row (or column) the only possible odd counts are 11 or 33. Since the total number of 11's is 55, the row-counts (and column-counts) must be a permutation of (3,1,1)(3,1,1).

Consequently exactly one row has three 11's and exactly one column has three 11's. Once we choose which row (3 choices) and which column (3 choices) are the "all-ones" row and column, the matrix is forced: put 11's in every cell of that chosen row and every cell of that chosen column. This yields exactly 3×3=93\times 3 = 9 distinct parity matrices, each with exactly five 11's and with every row and column summing to 1(mod2)1\pmod 2.

For each such parity pattern we can place the five odd numbers in the five cells in 5!5! ways and the four even numbers in the remaining four cells in 4!4! ways. Thus the number of favorable permutations of 1,,91,\dots,9 is 95!4!.9\cdot 5!\cdot 4!. The total number of permutations is 9!9!, so the desired probability is 95!4!9!=9(5!4!)9!=25920362880=114.\frac{9\cdot 5!\cdot 4!}{9!} = \frac{9\cdot (5!\,4!)}{9!} = \frac{25920}{362880} = \boxed{\frac{1}{14}}.