Maths Olympiad Prep

Library / /986 of 1394

Combinatorics Difficulty 5.5 AIME, harder Prove it United States

Problem:
Let f:{1,2,3,,9}{1,2,3,,9}f:\{1,2,3,\ldots ,9\} \to \{1,2,3,\ldots ,9\} be a permutation chosen uniformly at random from the 9!9! possible permutations. Compute the expected value of f(f(f(f(1))))2025 f s\underbrace{f(f(\cdots f(f(1))\cdots))}_{2025\ f\ s}.

Solution

Solution:
We first compute the probability that f(1)=1f(1) = 1. Note that f(1)=1f(1) = 1 if and only if 11 is part of a cycle whose length divides 20252025.
We claim that for any given kk, the probability that 11 is in a cycle of length kk is 19\frac{1}{9}. Indeed, the probability that f(1)1f(1) \neq 1 is 89\frac{8}{9}. Given this, there are 88 possible values remaining for f(f(1))f(f(1)), so the probability that f(f(1))1f(f(1)) \neq 1 is 78\frac{7}{8}, and so on. Finally, there are 10k10 - k possible values remaining for fk(1)f^{k}(1), so the probability that fk(1)=1f^{k}(1) = 1 given all previous assumptions is 110k\frac{1}{10 - k}. Thus, the probability that 11 is in a cycle of length kk is
897810k11k110k=19. \frac{8}{9} \cdot \frac{7}{8} \cdot \frac{10 - k}{11 - k} \cdot \frac{1}{10 - k} = \frac{1}{9}.
Hence, the probability that f2025(1)=1f^{2025}(1) = 1 is the probability that 11 is in a cycle of length 11, 33, 55, or 99, which is 49\frac{4}{9}.
If f(1)1f(1) \neq 1, then f(1)f(1) is equally likely to be any of 22 through 99 by symmetry, averaging 5.55.5.
Therefore, the expected value of f(1)f(1) is
491+595.5=72. \frac{4}{9} \cdot 1 + \frac{5}{9} \cdot 5.5 = \left\lceil \frac{7}{2} \right\rceil.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.