HMMT 二月 2022 · COMB 赛 · 第 10 题
HMMT February 2022 — COMB Round — Problem 10
题目详情
- Let S be a set of size 11. A random 12-tuple ( s , s , . . . , s ) of elements of S is chosen uniformly at 1 2 12 random. Moreover, let π : S → S be a permutation of S chosen uniformly at random. The probability a that s ̸ = π ( s ) for all 1 ≤ i ≤ 12 (where s = s ) can be written as where a and b are relatively i +1 i 13 1 b prime positive integers. Compute a .
解析
- Let S be a set of size 11. A random 12-tuple ( s , s , . . . , s ) of elements of S is chosen uniformly at 1 2 12 random. Moreover, let π : S → S be a permutation of S chosen uniformly at random. The probability a that s ̸ = π ( s ) for all 1 ≤ i ≤ 12 (where s = s ) can be written as where a and b are relatively i +1 i 13 1 b prime positive integers. Compute a . Proposed by: Daniel Zhu Answer: 1000000000004 Solution: Given a permutation π , let ν ( π ) be the number of fixed points of π . We claim that if we 12 12 10 + ν ( π ) − 1 fix π , then the probability that the condition holds, over the randomness of s , is . Note i 12 11 12 that a point in S is a fixed point of π if and only if the length of its cycle in π is 1, 2, 3, 4, or 6, 5 which happens with probability , as each cycle length from 1 to 11 is equally likely. Therefore, the 11 answer is 12 12 12 10 + ν ( π ) − 1 10 + 4 E = . π 12 12 11 11 12 Since 11 does not divide 10 + 4 this fraction is simplified. We now prove the claim. Instead of counting ( s , s , . . . , s ), we count tuples ( t , t , . . . , t ) so that 1 2 12 1 2 12 12 − i t ̸ = t for 1 ≤ i ≤ 11 and t ̸ = π ( t ). A bijection between the two is to let t = π ( s ). To i i +1 1 12 i i 12 do this, fix a t . If t is a fixed point of π , we need to count the possibilities for t , . . . , t so that 1 1 2 12 t ̸ = t , t ̸ = t , . . . , t ̸ = t . This can be done via recursion: if a is the number of t , . . . , t so 1 2 2 3 12 1 k 2 k +1 n that t ̸ = t , t ̸ = t , . . . , t ̸ = t , then a = 0, while for n ≥ 0 we have a = 9 a + 10(10 − a ) = 1 2 2 3 k +1 1 0 n +1 n n 1 n +1 11 10 1 12 10 − a ; thus a = 10 − 10 + · · · + 10 = (10 + 10). Similarly, if t is not a fixed point of n 11 1 11 1 12 12 π , there are (10 − 1) ways. Therefore, number of possible ( t , . . . , t ) is 1 n 11 12 10 1 12 12 12 12 12 12 ( ν ( π ) + (11 − ν ( π ))) + (10 ν ( π ) − (11 − ν ( π ))) = 10 + ν ( π ) − 1 , 11 11 as desired.