Secret Santa is a process that allows n people to give each other presents, so that each person gives a single present and receives a single present. At the beginning each of the n people write their name on a slip of paper and put the slip into a hat. Each person takes a random slip from the hat. If the slip has their name they draw another random slip from the hat and then put the slip with their name back into the hat. At the end everyone buys a Christmas present for the person whose name is on the slip they are holding. This process will fail if the last person draws their own name.
In this variation each of the n people gives and receives two presents. At the beginning each of the n people writes their name on two slips of paper and puts the slips into a hat (there will be 2n slips of paper in the hat). As before each person takes from the hat a random slip that does not contain their own name. Then the same person repeats this process thus ending up with two slips, neither of which contains that person's own name. Then the next person draws two slips in the same way, and so on. The process will fail if the last person gets at least one slip with their own name.
Define q(n) to be the probability of this happening. You are given q(3)=0.3611111111 and q(5)=0.2476095994 both rounded to 10 decimal places.
Find q(100) rounded to 10 decimal places.
Not the best code I've written as it struggles with n > 10. Anyway, who is gonna play Secret Santa with other 99 people. And you have to buy TWO gifts.
For small n, let p(xy) be the probability of the process fail when the first person draws slips from the x-th person and the y-th person. Then
q(3) = 1/3 * p(1) + 1/3 * p(2) + 1/3 * p(3)
Since the first person cannot have a slip from themselves, he/she keeps drawing until having two valid slips. They might draw slips up to four times. Then put the slip(s) with their name back.
p(1) = 1/5 * p(11) + 2/5 * p(12) + 2/5 * p(13)
p(2) = 2/5 * p(21) + 1/5 * p(22) + 2/5 * p(23)
p(3) = 2/5 * p(31) + 2/5 * p(32) + 1/5 * p(33)
To obtain p(1):
p(11) = 1/6 * p(1122) + 2/3 * p(1123) + 1/6 * p(1133) = 1/6 * p(22) + 2/3 * p(23) + 1/6 * p(33)
p(12) = 1/4 * p(121) + 1/4 * p(122) + 1/2 * p(123) = 1/4 * (1/3 * p(1212) + 2/3 * p(1213)) + 1/4 * p(22) + 1/2 * p(23) = 1/3 * p(22) + 2/3 * p(23)
p(13) = 2/3 * p(32) + 1/3 * p(33)
Following this idea, we have p(22) = 5/6, p(23) = p(32) = 1/3, p(33) = 0, which gives q(3) = 13/36
def p740(n=10):
@lru_cache(maxsize=None)
def f(a: tuple):
if len(a) == 2 * n - 2 and a.count(n) < 2: return 1.0 # fail
if a.count(n) == 2: return 0 # no fail
def draw_slips(slips, prob):
nonlocal res
if len(slips) - slips.count(i) == 2:
a = tuple(sorted(list(a) + [ii for ii in slips if ii != i]))
res += prob * f(a)
return
for s in list(remain_count.keys()):
if not remain_count[s]: continue
conditional_prob = remain_count[s] / (N - len(slips))
remain_count[s] -= 1
draw_slips(slips + [s], prob * conditional_prob)
remain_count[s] += 1
remain_count = Counter(list(range(1, n + 1)) * 2)
for k, v in Counter(a).items(): remain_count[k] -= v
res = 0
i = len(a) // 2 + 1
N = 2 * n - 2 * (i - 1)
draw_slips([], 1.0) # the i-th person draws two slips which cannot be i
return res
return f(())