Maths Olympiad Prep

Library / /1244 of 1394

Combinatorics Difficulty 5.9 AIME, harder Prove it United States

Problem:

Let [n][n] denote the set of integers {1,2,…,n}\{1,2, \ldots, n\}. 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)f^{k}(x) denotes the result of applying ff to xx kk times).

Solution

Solution:

Answer: 1n\frac{1}{n}

Given a function ff, define N(f)N(f) to be the number of numbers that are in the same cycle as 11 (including 11 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⋅1n P(N(f)=k)=\frac{n-1}{n} \cdot \frac{n-2}{n} \cdots \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⋅1nPn−1=(n−1n⋅n−2n⋯3n⋅2n)⋅n−1n⋅1n⇒Pn+Pn−1=(n−1n⋅n−2n⋯3n⋅2n)⋅1nPn−2=(n−1n⋅n−2n⋯3n)⋅n−2n⋅1n⇒Pn+Pn−1+Pn−2=(n−1n⋅n−2n⋯3n)⋅1n⋯⇒∑k=1nPk=1 \begin{array}{rlrl} P_{n} & =\left(\frac{n-1}{n} \cdot \frac{n-2}{n} \cdots \frac{3}{n} \cdot \frac{2}{n} \cdot \frac{1}{n}\right) \cdot \frac{n}{n} & \cdot \frac{1}{n} \\ P_{n-1} & =\left(\frac{n-1}{n} \cdot \frac{n-2}{n} \cdots \frac{3}{n} \cdot \frac{2}{n}\right) \cdot \frac{n-1}{n} & \cdot \frac{1}{n} \\ \Rightarrow P_{n}+P_{n-1} & =\left(\frac{n-1}{n} \cdot \frac{n-2}{n} \cdots \frac{3}{n} \cdot \frac{2}{n}\right) & \cdot \frac{1}{n} \\ P_{n-2} & =\left(\frac{n-1}{n} \cdot \frac{n-2}{n} \cdots \frac{3}{n}\right) \cdot \frac{n-2}{n} & \cdot \frac{1}{n} \\ \Rightarrow P_{n}+P_{n-1}+P_{n-2} & =\left(\frac{n-1}{n} \cdot \frac{n-2}{n} \cdots \frac{3}{n}\right) & \cdot \frac{1}{n} \\ & \cdots & & \\ \Rightarrow \sum_{k=1}^{n} P_{k} & =1 & & \end{array}
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: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.