Maths Olympiad Prep

Library / /183 of 1394

Combinatorics Difficulty 4.9 AIME Find the answer United States

Problem:
Let π\pi be a uniformly random permutation of the set {1,2,,100}\{1,2, \ldots, 100\}. The probability that π20(20)=20\pi^{20}(20)=20 and π21(21)=21\pi^{21}(21)=21 can be expressed as ab\frac{a}{b}, where aa and bb are relatively prime positive integers. Compute 100a+b100a+b. (Here, πk\pi^{k} means π\pi iterated kk times.)

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

Solution:
We look at the cycles formed by π\pi. Let ordπ(n)\operatorname{ord}_{\pi}(n) denote the smallest mm such that πm(n)=n\pi^{m}(n)=n. In particular, the condition implies that ordπ(20)20\operatorname{ord}_{\pi}(20) \mid 20 and ordπ(21)21\operatorname{ord}_{\pi}(21) \mid 21.

Claim 1. 2020 and 2121 cannot be in the same cycle.
Proof. If 2020 and 2121 were in the same cycle, then x=ordπ(20)=ordπ(21)x=\operatorname{ord}_{\pi}(20)=\operatorname{ord}_{\pi}(21) for some xx. Then x>1x>1 since the cycle contains both 2020 and 2121, but x20,x21x|20, x|21 implies x=1x=1, a contradiction.

Claim 2. The probability that a=ordπ(20),b=ordπ(21)a=\operatorname{ord}_{\pi}(20), b=\operatorname{ord}_{\pi}(21) for some fixed a,ba, b such that a+b100a+b \leq 100 is 199100\frac{1}{99 \cdot 100}.
Proof. We can just count these permutations. We first choose a1a-1 elements of [100]{20,21}[100] \setminus \{20,21\} to be in the cycle of 2020, then we similarly choose b1b-1 to be in the cycle of 2121. We then have (a1)!(a-1)! ways to reorder within the cycle of 2020, (b1)!(b-1)! ways to reorder within the cycle of 2121, and (100ab)!(100-a-b)! ways to permute the remaining elements. The total number of ways is just
98!(a1)!(b1)!(100ab)!(a1)!(b1)!(100ab)!=98!, \frac{98!}{(a-1)!(b-1)!(100-a-b)!} \cdot (a-1)!(b-1)!(100-a-b)! = 98!,
so the probability this happens is just 98!100!=19900\frac{98!}{100!}=\frac{1}{9900}.

Now, since ordπ(20)20\operatorname{ord}_{\pi}(20) \mid 20 and ordπ(21)21\operatorname{ord}_{\pi}(21) \mid 21, we have 66 possible values for ordπ(20)\operatorname{ord}_{\pi}(20) and 44 for ordπ(21)\operatorname{ord}_{\pi}(21), so in total we have a 649900=2825\frac{6 \cdot 4}{9900}=\frac{2}{825} probability that the condition is satisfied.

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.