HMMT 二月 2010 · 冲刺赛 · 第 32 题

英文解析

32. [ 21 ] There are 101 people participating in a Secret Santa gift exchange. As usual each person israndomly assigned another person for whom (s)he has to get a gift, such that each person gives andreceives exactly one gift and no one gives a gift to themself. What is the probability that the firstperson neither gives gifts to or receives gifts from the second or third person? Express your answer asa decimal rounded to five decimal places.
    Answer: 0 . 96039 Let D denote the number of derangements of { 1 , 2 , . . . , k } . (A derangement is akpermutation 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 → Ydenote 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 itinto 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 asn − 1
    a single vertex, and since B 6 → A , we have a derangement. Similarly, there are D ways to haven − 1
    B → A 6 → B . Thirdly, there are D ways to have A → B → A , since D says how many waysn − 2 n − 2
    the other n − 2 people can exchange their gifts. So there are 2 D + D ways to have a conflictn − 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 andn − 2
    D ways for B → A → C → B to occur. We get the same results when B and C are reversed. Thisn − 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 isna great approximation), we find that the probability of no conflicts ise
    ( ) ( )
    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)
    Guts Roundn
    Substitute m = n − 1 (this makes m = 100, so the expression is easier to evaluate) to get a probabilityof
    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.