HMMT 二月 2025 · 冲刺赛 · 第 18 题

HMMT February 2025 — Guts Round — Problem 18

[11] Let f : { 1 , 2 , 3 , . . . , 9 } → { 1 , 2 , 3 , . . . , 9 } be a permutation chosen uniformly at random from the 9! possible permutations. Compute the expected value of f ( f ( · · · f ( f ( 1)) · · · )). | {z } 2025 f ’s

解析

[11] Let f : { 1 , 2 , 3 , . . . , 9 } → { 1 , 2 , 3 , . . . , 9 } be a permutation chosen uniformly at random from the 9! possible permutations. Compute the expected value of f ( f ( · · · f ( f ( 1)) · · · )). | {z } 2025 f ’s Proposed by: Linus Yifeng Tang 7 Answer: 2 Solution: We first compute the probability that f (1) = 1. Note that f (1) = 1 if and only if 1 is part of a cycle whose length divides 2025. 1 We claim that for any given k , the probability that 1 is in a cycle of length k is . Indeed, the 9 8 probability that f (1) ̸ = 1 is . Given this, there are 8 possible values remaining for f ( f (1)), so the 9 7 probability that f ( f (1)) ̸ = 1 is , and so on. Finally, there are 10 − k possible values remaining for 8 1 k k f (1), so the probability that f (1) = 1 given all previous assumptions is . Thus, the probability 10 − k that 1 is in a cycle of length k is 8 7 10 − k 1 1 · · · · · = . 9 8 11 − k 10 − k 9 2025 Hence, the probability that f (1) = 1 is the probability that 1 is in a cycle of length 1, 3, 5, or 9, 4 which is . 9 If f (1) ̸ = 1, then f (1) is equally likely to be any of 2 through 9 by symmetry, averaging 5 . 5. Therefore, the expected value of f (1) is 4 5 7 · 1 + · 5 . 5 = . 9 9 2