HMMT 二月 2010 · 冲刺赛 · 第 32 题
HMMT February 2010 — Guts Round — Problem 32
题目详情
- [ 21 ] There are 101 people participating in a Secret Santa gift exchange. As usual each person is randomly assigned another person for whom (s)he has to get a gift, such that each person gives and receives exactly one gift and no one gives a gift to themself. What is the probability that the first person neither gives gifts to or receives gifts from the second or third person? Express your answer as a decimal rounded to five decimal places.
解析
- [ 21 ] There are 101 people participating in a Secret Santa gift exchange. As usual each person is randomly assigned another person for whom (s)he has to get a gift, such that each person gives and receives exactly one gift and no one gives a gift to themself. What is the probability that the first person neither gives gifts to or receives gifts from the second or third person? Express your answer as a decimal rounded to five decimal places. Answer: 0 . 96039 Let D denote the number of derangements of { 1 , 2 , . . . , k } . (A derangement is a k permutation in which no element appears in its original position.) Call the first three people A , B , and C . Let X → Y denote that X gives a gift to Y and let X 6 → Y denote that X gives a gift to anyone other than Y . We are fine unless we have A → B , B → A , A → C , or C → A . We will compute the number of ways for various things to occur, then combine it into what we want. There are D ways to have A → B 6 → A . This is because if A → B , we can treat A and B as n − 1 a single vertex, and since B 6 → A , we have a derangement. Similarly, there are D ways to have n − 1 B → A 6 → B . Thirdly, there are D ways to have A → B → A , since D says how many ways n − 2 n − 2 the other n − 2 people can exchange their gifts. So there are 2 D + D ways to have a conflict n − 1 n − 2 between A and B . Similarly, there are 2 D + D ways to have a conflict between A and C . n − 1 n − 2 Using similar arguments, we can show that there are D ways for B → A → C 6 → B to occur and n − 2 D ways for B → A → C → B to occur. We get the same results when B and C are reversed. This n − 3 gives 2 D + 2 D ways for a conflict to occur within all three people. n − 2 n − 3 By the Principle of Inclusion-Exclusion, the total number of ways to have a conflict is (# conflicts between A and B )+(# conflicts between A and C ) − (# conflicts between A , B , and C ) , which evaluates to 4 D − 2 D . n − 1 n − 3 n ! Approximating D as (the actual formula is this quantity rounded to the nearest integer, so this is n e a great approximation), we find that the probability of no conflicts is ( ) ( ) 4 D − 2 D ( n − 1)! /e ( n − 3)! /e n ( n − 1)( n − 2) − 4( n − 1)( n − 2) − 2 n − 1 n − 3 1 − ≈ 1 − 4 − 2 = . D n ! /e n ! /e n ( n − 1)( n − 2) n Guts Round Substitute m = n − 1 (this makes m = 100, so the expression is easier to evaluate) to get a probability of 3 2 3 2 m − m − 4 m + 4 m − 2 m − 4 m + 3 m − 2 1,000,000 − 40,000 + 300 − 2 960298 = = = 3 3 m − m m − m 100 · 9999 100 · 9999 = 0 . 960208 · (1 . 000100010001 . . . ) = 0 . 960208 + 0 . 0000960208 + . . . = 0 . 9603940 . . . To five decimal places, the desired probability is 0.96039.