HMMT-Feb 2021 guts, Problem 17

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

Solution: Solution: We write $k=11 q+r$ for integers $q, r$ with $0 \leq r<11$. There are $q$ multiples of 11 from 1 to $k$, inclusive, so our probability is $\frac{a}{b}=\frac{q}{11 q+r}$. Let $d=\operatorname{gcd}(q, r)=\operatorname{gcd}(q, 11 q+r)$, so that the fraction $\frac{q / d}{(11 q+r) / d}$ is how we would write $\frac{q}{11 q+r}$ in simplified form. Since we require that $a$ and $b$ be relatively prime, we find $a=\frac{q}{d}$ and $b=\frac{11 q+r}{d}$. Plugging these into the equation $k=100 a+b$, we find $11 q+r=100 \frac{q}{d}+\frac{11 q+r}{d}$, or $d(11 q+r)=111 q+r$. Since $d$ divides $r$ and $r \leq 10$, we have $d \leq 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 $\operatorname{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. $\fbox{1000}$.

Answer: 1000