35. [20] A random permutation of $\{1,2, \ldots, 100\}$ is given. It is then sorted to obtain the sequence $(1,2, \ldots, 100)$ as follows: at each step, two of the numbers which are not in their correct positions are selected at random, and the two numbers are swapped. If $s$ is the expected number of steps (i.e. swaps) required to obtain the sequence $(1,2, \cdots, 100)$, then estimate $A=\lfloor s\rfloor$. An estimate of $E$ earns $\max \left(0,\left\lfloor 20-\frac{1}{2}|A-E|\right\rfloor\right)$ points.
Answer: 2427
Solution: Let $f(n)$ be the expected number of steps if there are $n$ elements out of order. Let's consider one of these permutations and suppose that $a$ and $b$ are random elements that are out of order. The probability that swapping $a$ and $b$ sends $a$ to the proper place is $\frac{1}{n-1}$, and the probability that it sends $b$ to the proper place is $\frac{1}{n-1}$. Thus we can approximate
$$
f(n) \approx 1+\frac{2}{n-1} f(n-1)+\frac{n-3}{n-1} f(n) .
$$
(The chance that both get sent to the right place decreases the overall probability that the number of fixed points increases, but also decreases the expected number of moves after the swap. These effects largely cancel out.)
As a result, we conclude that
$$
f(n) \approx f(n-1)+\frac{n-1}{2},
$$
and since $f(0)=0$ we have $f(n) \approx \frac{n(n-1)}{4}$. At the beginning, the expected number of elements that are in the right place is 1 , so the answer is approximately $f(99) \approx \frac{99 \cdot 98}{4} \approx 2425$. This is good enough for 19 points.