Finding the prisoners' names

This is yet another of those crazy warden and mathematical prisoner puzzles.

This time, there are $2n$ prisoners (each with a distinct name).

The warden has a room with $2n$ boxes, each box has the name of exactly one prisoner, and each prisoner's name appears in some box (picked randomly by the warden).

The game the warden plays is that each prisoner goes independently (one by one) in a room and points at some $n$ of the boxes. The goal being that each prisoner should choose the box which contains their own name. If any one of the prisoners does not then they all lose the game. The prisoners aren't allowed to communicate in any way (with each other) what boxes they picked.

If each prisoner picked $n$ boxes at random, then the probability that they win the game (each picks their own name) is $\dfrac{1}{2^n}$ which is pretty small.

They are allowed to choose a strategy before any of them enter the room.

Show that there is a constant $c \gt 0$ (independent of $n$) and a strategy such that the prisoners win the game with probability at least $c$.

Limit of iterated x + 1/x

Suppose $x_1 = 1$ and

$$x_{n+1} = x_n + \frac{1}{x_n}$$

Find

$$\lim_{n \to \infty} \frac{x_n^2 - 2n}{\log n}$$

Expected number of correct coats

This is a classic:


$N$ people attend a party and deposit their ($N$) coats with the coat keeper.

At the end of the party, everyone is drunk (even the coat keeper). The coat keeper hands out a random coat to anyone who comes to claim a coat. Since the owner of the coats are drunk too, no one notices.

What is the expected number of people that get their correct coat back?