Strange Separating

Let the answer for $n$ people be $g(n)$ . Consider the card the first person draws, $c_1$ . If it shows $c_1=1$ , a group is formed, and we can exclude person 1 from subsequent considerations, making our answer $1+g(n-1)$ . If it shows $c_1=x\not=1$ , we can unite persons 1 and $x$ into a new person with number 1 and drawn card $c_x$ , the card person $x$ drew. Thus in this case the answer is simply $g(n-1)$ . This leads to the recurrence relation $g(n)=\frac{1}{n}+g(n-1)$ . Thus $g(n)=\displaystyle\sum_{i=1}^n \frac{1}{i}\approx \ln{n}+\gamma$ , with $\gamma\approx0.5772$ being the Euler-Mascheroni constant. For $n=1000$ , we have $g(1000)\approx7.485$ .