On a camp, there are n boys and n girls, and each person sleeps in a different tent. During each night, each boy randomly picks one girl's tent to visit. Each girl does the same with a boy's tent. Initially, one person's is infected by a virus. If you visit an infected person's tent, you are infected and you will be contagious contagious after the night, but not yet during the night (so, the order of visiting is irrelevant). What is the chance to be healthy after k nights? Give a simple formula for k ≥ 1.

Denote by b_{k} and g_{k} the probability for a boy/girl to be healthy after k nights. To be healthy after k+1 nights, one needs to be healthy after k nights, and visit a healthy person's tent on the k+1 'th night. Hence, it follows that b_{k+1} = b_{k} g_{k} and g_{k+1} = g_{k} b_{k}.

Since the formulas are identical, b_{k} = m_{k} for all k ≥ 1, and we may write this probability simply as p_{k}, independent of their gender. Hence, the formulas reduce to p_{k+1} = p_{k}^{2}. This yields an easy general formula: p_{k} = p_{k-1}^{2} = p_{k-2}^{4} = p_{k-3}^{8} = ... = p_{1}^{2k-1}. Since we start with b_{0} and m_{0} equal to 1 and 1-1/n (in some order), this yields p_{1} = 1 - 1/n, which completes the formula.

This is not as easy as it looks. In less competitive environments (e.g. exams for non-math majors), it may be wise to split the problem in parts: computing p_{1}, proving the quadratic recursion formula and actually converting it to a solution.