How many trials for Secret Santa?

Probability Level 2

For a Secret Santa, the following procedure is followed. The name of each of the participants is written on a piece of paper. These 'tickets' are folded and put into a bowl. Each of the participants takes a random note from the bowl, and inspects it silently. However, as soon as someone has their own ticket, they announce so. In that case all tickets are recollected into the bowl and a second trial starts. This continues until no one has the ticket with their own name.

As the number of participants approaches infinity, how many trials are needed, on average?

Attention: enter your answer as follows:

  • If you think this is a whole number, just enter it
  • If it is infinity, enter -1
  • If it is a non-integer value, enter ⌊ 10000 × { 10000 x } ⌋ \left \lfloor 10000×\{10000x\} \right \rfloor as your answer, so if for example the answer would be 1.23456789876 1.23456789876 , then enter 6789 6789


The answer is 8182.

K T by K T , 55, Netherlands

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

1 solution

Lovro Cupic
Mar 16, 2020

Number of derangements of n n objects is ⌊ n ! e ⌉ \lfloor \frac{n!}{e}\rceil . Probability of a random trial succeeding is therefore 1 e \frac{1}{e} which means that expected number of trials is e e .

1 Helpful 0 Interesting 0 Brilliant 0 Confused

Thank you for posting a solution, correct and concise.

Since I believe providing a link or explanation for the expression [ n ! / e ] [n!/e] would add value for most readers, so here: http://oeis.org/wiki/Number of derangements.

K T - 1 year, 2 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...