HMMT 二月 2023 · COMB 赛 · 第 8 题
HMMT February 2023 — COMB Round — Problem 8
题目详情
- A random permutation a = ( a , a , . . . , a ) of (1 , 2 , . . . , 40) is chosen, with all permutations being 1 2 40 equally likely. William writes down a 20 × 20 grid of numbers b such that b = max( a , a ) for ij ij i j +20 all 1 ≤ i, j ≤ 20, but then forgets the original permutation a . Compute the probability that, given the values of b alone, there are exactly 2 permutations a consistent with the grid. ij
解析
- A random permutation a = ( a , a , . . . , a ) of (1 , 2 , . . . , 40) is chosen, with all permutations being 1 2 40 equally likely. William writes down a 20 × 20 grid of numbers b such that b = max( a , a ) for ij ij i j +20 all 1 ≤ i, j ≤ 20, but then forgets the original permutation a . Compute the probability that, given the values of b alone, there are exactly 2 permutations a consistent with the grid. ij Proposed by: Zixiang Zhou 10 Answer: 13 Solution: We can deduce information about a from the grid b by looking at the largest element of it, say m . If m fills an entire row, then the value of a corresponding to this row must be equal to m . Otherwise, m must fill an entire column, and the value of a corresponding to this column must be equal to m . We can then ignore this row/column and continue this reasoning recursively on the remaining part of the grid. Near the end, there are two cases. We could have a 1 × 1 remaining grid, where there are 2 permutations a consistent with b . We could also have a case where one of the dimensions of the remaining grid is 1, the other dimension is at least 2 (say k ), and the number k + 1 fills the entire remaining grid. In that case, there are k ! ways to arrange the other elements 1 , . . . , k . It follows that there are exactly 2 permutations a consistent with the grid if and only if one of 1 and 2 is assigned to a row and the other is assigned to a column, or they are both assigned to the same type and 3 is assigned to the opposite type. The probability that this does not occur is the probability that 19 18 18 3 1 , 2 , 3 are all assigned to the same type, which happens with probability · = = , so the 39 38 2 · 39 13 3 10 answer is 1 − = . 13 13