HMMT 二月 2017 · COMB 赛 · 第 8 题
HMMT February 2017 — COMB Round — Problem 8
题目详情
- Kelvin and 15 other frogs are in a meeting, for a total of 16 frogs. During the meeting, each pair of 1 distinct frogs becomes friends with probability . Kelvin thinks the situation after the meeting is cool 2 if for each of the 16 frogs, the number of friends they made during the meeting is a multiple of 4. Say a that the probability of the situation being cool can be expressed in the form , where a and b are b relatively prime. Find a .
解析
- Kelvin and 15 other frogs are in a meeting, for a total of 16 frogs. During the meeting, each pair of 1 distinct frogs becomes friends with probability . Kelvin thinks the situation after the meeting is cool 2 if for each of the 16 frogs, the number of friends they made during the meeting is a multiple of 4. Say a that the probability of the situation being cool can be expressed in the form , where a and b are b relatively prime. Find a . Proposed by: Yang Liu Consider the multivariate polynomial ∏ (1 + x x ) i j 1 ≤ i<j ≤ 16 16 We’re going to filter this by summing over all 4 16-tuples ( x , x , . . . , x ) such that x = ± 1 , ± i. 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 get the 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’re j ( ) 16 121 all − 1. Total is 2 . (120 = . ) 2 Case 2: i appears, but − i does not. Then all the remaining x must be all 1 or all − 1. This contributes j 15 105 15 105 113 113 a sum of (1 + i ) · 2 + (1 − i ) · 2 = 2 . i can be at any position, so we get 16 · 2 . 113 Case 3: − i appears, but i does not. Same contribution as above. 16 · 2 . Case 4: Both i and − i appear. Then all the rest of the x must be all 1 or all − 1 . This contributes a j 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 107 240 · 2 . 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 = 120 2 1167 . 41 2 Therefore, the answer is 1167 .