HMMT February

The key claim is the following. Claim: The sum in the problem is equal to the number of solutions of $2 x+3 y \leq 300$ where $x, y$ are positive integers. Proof. The sum in the problem is the same as counting the number of triples $(a, b, d)$ of positive integers such that $\operatorname{gcd}(a,$ b)=1$and$d(2 a+3 b) $\leq$ 300$. Now, given such$(a, b, d)$, we biject it to the pair$(x, y)$described in the claim by$x=d a$and$x=d b$. This transformation can be reversed by$$d=\operatorname{gcd}(x,$ y)$,$a=x / d$, and$b=y / d, implying that it is indeed a bijection, so the sum is indeed equal to the number of $\operatorname{such}(x,$ y). Hence, we wish to count the number of positive integer solutions to $2 x+3 y \leq 300$. One way to do this is via casework on $y$, which we know to be an integer less than 100: - If $y$ is even, then $y=2 k$ for $1 \leq k \leq 49$. Fixing $k$, there are exactly $\frac{300-6 k}{2}=150-3 k$ values of $x$ which satisfy the inequality, hence the number of solutions in this case is $$\sum_{k=1}^{49}(150-3 k)=\frac{150 \cdot 49}{2}=3675$$ - If $y$ is odd, then $y=2 k-1$ for $1 \leq k \leq 50$. Fixing $y$, there are exactly $\frac{302-6 k}{2}=151-3 k$ values of $x$ which satisfy the inequality, hence the number of solutions in this case is $$\sum_{k=1}^{50}(151-3 k)=\frac{149 \cdot 50}{2}=3725$$ The final answer is $3675+3725=7400$.