Maths Olympiad Prep

Library / /691 of 860

Combinatorics Difficulty 5.4 AIME, harder Find the answer

We randomly choose a function f:[n]→[n]f:[n] \rightarrow[n], out of the nnn^{n} possible functions. We also choose an integer aa uniformly at random from [n][n]. Find the probability that there exist positive integers b,c≥1b, c \geq 1 such that fb(1)=af^{b}(1)=a and fc(a)=1f^{c}(a)=1. (fk(x)\left(f^{k}(x)\right. denotes the result of applying ff to xkx k times).

A number or a short expression. Spacing and $ signs are ignored.

Solution

Given a function ff, define N(f)N(f) to be the number of numbers that are in the same cycle as 1 (including 1 itself), if there is one, and zero if there is no such cycle. The problem is equivalent to finding E(N(f))/n\mathbb{E}(N(f)) / n. Note that P(N(f)=k)=n−1n⋅n−2n⋯⋯⋅n−k+1n⋅1nP(N(f)=k)=\frac{n-1}{n} \cdot \frac{n-2}{n} \cdots \cdots \cdot \frac{n-k+1}{n} \cdot \frac{1}{n} and it suffices to compute ∑k=1nPk\sum_{k=1}^{n} P_{k} where Pk=knP(N(f)=k)P_{k}=\frac{k}{n} P(N(f)=k). Observe that Pn=(n−1n⋅n−2n⋯⋯3n⋅2n⋅1n)⋅nn⋅1nP_{n}=\left(\frac{n-1}{n} \cdot \frac{n-2}{n} \cdots \cdots \frac{3}{n} \cdot \frac{2}{n} \cdot \frac{1}{n}\right) \cdot \frac{n}{n} \cdot \frac{1}{n} Pn−1=(n−1n⋅n−2n⋯⋯3n⋅2n)⋅n−1n⋅1nP_{n-1}=\left(\frac{n-1}{n} \cdot \frac{n-2}{n} \cdots \cdots \frac{3}{n} \cdot \frac{2}{n}\right) \cdot \frac{n-1}{n} \cdot \frac{1}{n} ⇒Pn+Pn−1=(n−1n⋅n−2n⋯⋯3n⋅2n)⋅1n\Rightarrow P_{n}+P_{n-1}=\left(\frac{n-1}{n} \cdot \frac{n-2}{n} \cdots \cdots \frac{3}{n} \cdot \frac{2}{n}\right) \cdot \frac{1}{n} Pn−2=(n−1n⋅n−2n⋯⋯3n)⋅n−2n⋅1nP_{n-2}=\left(\frac{n-1}{n} \cdot \frac{n-2}{n} \cdots \cdots \frac{3}{n}\right) \cdot \frac{n-2}{n} \cdot \frac{1}{n} ⇒Pn+Pn−1+Pn−2=(n−1n⋅n−2n⋯⋯3n)⋅1n\Rightarrow P_{n}+P_{n-1}+P_{n-2}=\left(\frac{n-1}{n} \cdot \frac{n-2}{n} \cdots \cdots \frac{3}{n}\right) \cdot \frac{1}{n} ⋯⋅1n\cdots \cdot \frac{1}{n} Therefore the answer is 1n\frac{1}{n}.

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: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.