Question 159
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.