Problem 09

Problem 09

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 bk and gk 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 bk+1 = bk gk and gk+1 = gk bk.

Since the formulas are identical, bk = mk for all k ≥ 1, and we may write this probability simply as pk, independent of their gender. Hence, the formulas reduce to pk+1 = pk2. This yields an easy general formula: pk = pk-12 = pk-24 = pk-38 = ... = p12k-1. Since we start with b0 and m0 equal to 1 and 1-1/n (in some order), this yields p1 = 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 p1, proving the quadratic recursion formula and actually converting it to a solution.