Too many valentines

The optimum strategy would be for valentine $i$ to start with envelope $i$ which contains the number $r_{k}$ (May or may not be equal to $i$ ) and go to envelope $r_{k}$ and continue this cycle till she either opens $\frac{n}{2}$ envelopes or finds the number. Since each envelope contains only one number inside, it will eventually form a chain of length between $1$ and $n$ which loops back to the envelope you started with.

The probability of the chain length being $a$ is $\frac{a-1}{a} \times \frac{a-2}{a-1} \times . . . \times \frac{2}{3} \times \frac {1}{2} \times 1= \frac{1}{a}$ Since each person is only allowed to open $\frac{n}{2}$ envelopes, we simply need to evaluate the probability of a chain length greater than $\frac{n}{2}$ occuring and subtract it from $1$

$P = 1 - \lim_{n \Rightarrow \infty} \sum_{x=\frac{n}{2} +1}^{n} \frac{1}{x}$ $P = 1-ln(2)$