HMMT 二月 2017 · COMB 赛 · 第 8 题

英文解析

8. Kelvin and 15 other frogs are in a meeting, for a total of 16 frogs. During the meeting, each pair ofdistinct frogs becomes friends with probability . Kelvin thinks the situation after the meeting is cool 1
   if for each of the 16 frogs, the number of friends they made during the meeting is a multiple of 4. Say 2
   that the probability of the situation being cool can be expressed in the form , where a and b areabrelatively prime. Find a .
   Proposed by: Yang Liu
   Consider the multivariate polynomial
   ∏
   (1 + x x )
   i j
   1 ≤ i<j ≤ 16
   We’re going to filter this by summing over all 4 16-tuples ( x , x , . . . , x ) such that x = ± 1 , ± i.16
   1 2 16 j
   2 2
   Most of these evaluate to 0 because i = ( − i ) = − 1 , and 1 · − 1 = − 1 . If you do this filtering, you getthe following 4 cases:
   Case 1: Neither of i or − i appears. Then the only cases we get are when all the x are 1, or they’rej
   ( )
   12116
   all − 1. Total is 2 . (120 = . )
   Case 2: i appears, but − i does not. Then all the remaining x must be all 1 or all − 1. This contributes 2
   15 105 15 105 113 113 ja sum of (1 + i ) · 2 + (1 − i ) · 2 = 2 . i can be at any position, so we get 16 · 2 .
   Case 3: − i appears, but i does not. Same contribution as above. 16 · 2 .113
   Case 4: Both i and − i appear. Then all the rest of the x must be all 1 or all − 1 . This contributes aj
   14 14 91 107
   sum of 2 · (1 + i ( − i )) · (1 + i ) · (1 − i ) · 2 = 2 . i and − i can appear in 16 · 15 places, so we get
   240 · 2 .107
   89 82 75
   16 32 2 +16 · 2 +240 · 2
   So the final answer is this divided a factor for our filter. (4 = 2 . ) So our final answer is =
   2120
   1167
   .
   Therefore, the answer is 1167 .241