HMMT 十一月 2023 · GEN 赛 · 第 9 题
HMMT November 2023 — GEN Round — Problem 9
题目详情
- An entry in a grid is called a saddle point if it is the largest number in its row and the smallest number in its column. Suppose that each cell in a 3 × 3 grid is filled with a real number, each chosen independently and uniformly at random from the interval [0 , 1] . Compute the probability that this grid has at least one saddle point. ◦
解析
- An entry in a grid is called a saddle point if it is the largest number in its row and the smallest number in its column. Suppose that each cell in a 3 × 3 grid is filled with a real number, each chosen independently and uniformly at random from the interval [0 , 1] . Compute the probability that this grid has at least one saddle point. Proposed by: Benjamin Shimabukuro 3 Answer: 10 Solution: With probability 1 , all entries of the matrix are unique. If this is the case, we claim there can only be one saddle point. To see this, suppose A and A are both saddle points. They cannot ij kl be in the same row, since they cannot both be the greatest number in the same row, and similarly they cannot be in the same column, since they cannot both be the least number in the same column. If they are in different rows and different columns, then A < A and A > A , so A < A . However, we ij il kl il ij kl also have A > A and A < A , so A > A . This is a contradiction, so there is only one saddle ij kj kl kj ij kl point. Each entry of the matrix is equally likely to be a saddle point by symmetry, so we can just multiply the probability that A is a saddle point by 9 to find the answer. For A to be a saddle point, it 11 11 must be greater than A and A , but less than A and A . There are 5! = 120 equally likely ways 21 31 12 13 that the numbers A , A , A , A , A could be arranged in increasing order, and 4 of them work, so 11 12 13 21 31 1 the probability that A is a saddle point is . Therefore, the probability that A has a saddle point 11 30 1 3 is 9 · = . 30 10 ◦