HMMT 二月 2021 · 冲刺赛 · 第 17 题

HMMT February 2021 — Guts Round — Problem 17

[12] Let k be the answer to this problem. The probability that an integer chosen uniformly at random a from { 1 , 2 , . . . , k } is a multiple of 11 can be written as for relatively prime positive integers a and b . b Compute 100 a + b .

解析

[12] Let k be the answer to this problem. The probability that an integer chosen uniformly at random a from { 1 , 2 , . . . , k } is a multiple of 11 can be written as for relatively prime positive integers a and b . b Compute 100 a + b . Proposed by: Carl Schildkraut, Hahn Lheem Answer: 1000 Solution: We write k = 11 q + r for integers q, r with 0 ≤ r < 11. There are q multiples of 11 from 1 q a to k , inclusive, so our probability is = . Let d = gcd( q, r ) = gcd( q, 11 q + r ), so that the fraction b 11 q + r q/d q is how we would write in simplified form. Since we require that a and b be relatively (11 q + r ) /d 11 q + r q 11 q + r prime, we find a = and b = . d d q 11 q + r Plugging these into the equation k = 100 a + b , we find 11 q + r = 100 + , or d (11 q + r ) = 111 q + r . d d Since d divides r and r ≤ 10, we have d ≤ 10. If we test the case d = 10, our equation becomes q = 9 r . Since r = 10 is the only valid value that is a multiple of d , we get q = 90 and k = 1000. 10 is, in fact, the gcd of q and r , so we have found that k = 1000 satisfies the problem. Testing other values of d does not produce a valid answer.