PROBLEM LINKS
DIFFICULTY
MEDIUM
EXPLANATION
The chef chooses a random derangement of the chairs as the follow-ups. If we focus our attention on a single guest, that guest will be back in their original seat after R ringings if and only if the cycle they belong to has a length that divides R. Thus, for each divisor D of R not exceeding N, we count the number of derangements where a specific element (say, the first one) belongs to a cycle of length D, then divide by the total number of derangements. This will give us the probability of a single guest being back in his/her original seat. To get the expected number of guests, simply multiply by the total number of guests. The total number of derangements where the first element belongs to a cycle of length D is the total number of possible cycles ((N-1)!/(N-D)!), times the number of derangements on (N-D) elements. The number of derangements is calculated by the recurrence derange[0]=1, derange[1]=0, derange[i]=(i-1)*(derange[i-1]+derange[i-2]).
SETTER’S SOLUTION
Can be found here.
TESTER’S SOLUTION
Can be found here.