HMMT 十一月 2022 · 冲刺赛 · 第 33 题
HMMT November 2022 — Guts Round — Problem 33
题目详情
- [17] A group of 101 Dalmathians participate in an election, where they each vote independently on either candidate A or B with equal probability. If X Dalmathians voted for the winning candidate, the expected 2 a value of X can be expressed as for positive integers a, b with gcd( a, b ) = 1. Find the unique positive b integer k ≤ 103 such that 103 | a − bk . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . HMMT November 2022, November 12, 2022 — GUTS ROUND Organization Team Team ID#
解析
- [17] A group of 101 Dalmathians participate in an election, where they each vote independently on either candidate A or B with equal probability. If X Dalmathians voted for the winning candidate, 2 a the expected value of X can be expressed as for positive integers a, b with gcd( a, b ) = 1. Find the b unique positive integer k ≤ 103 such that 103 | a − bk . Proposed by: William Wang Answer: 51 2 Solution: Claim: with 101 replaced with 2 k + 1, the expectation of X is 2 k (2 k + 1)(2 k + 2) 2 k (2 k + 1) + . 2 k +1 2 4 The answer is this value taken modulo 103, which can be calculated by noting that the integers modulo 101 103 form a finite field. Note that the multiplicative inverse of 4 is 26, the multiplicative inverse of 2 is 2 by Fermat’s little theorem, and the multiplicative inverse of 102! is 102 by Wilson’s theorem. Now we will justify the Claim. Let I be the indicator random variable of the i -th Dalmathian voting i for the winning candidate ( I = 1 if i votes for the winning candidate, and I = 0 otherwise). Then we i i want to find 2 E [( I + · · · + I ) ] . 1 2 k +1 By symmetry and linearity, this is 2 (2 k + 1) E [ I ] + (2 k + 1)(2 k ) E [ I I ] . 1 2 1 2 Now, we note that E [ I ] = E [ I ] is just the probability that Dalmathian 1 votes for the winning 1 1 candidate. WLOG, say that they vote for A . Then we want to find the probability that at least k of the remaining 2 k Dalmathians also vote for A . By symmetry, this is equal to the probability that exactly k vote for A , plus half of the remaining probability. This is: 2 k 1 k
- . 2 k +1 2 2 Next, we must calculate E [ I I ]. In order for I I to be 1, they must Dalmathians vote for the same 1 2 1 2 candidate (1 / 2 chance), and then this candidate has to win (at least k − 1 out of the remaining 2 k − 1 Dalmathians vote for that candidate). Overall, this occurs with probability ! 2 k − 1 1 1 k − 1
- . 2 k − 1 2 2 2 Now when we add the two terms together, we get ! ! 2 k − 1 2 k 1 1 k − 1 k
- (2 k + 1) + (2 k + 1)(2 k ) + . 2 k +1 2 k 2 2 4 2 With some simplification, you get the expression in the Claim.