Maths Olympiad Prep

Library / /1065 of 1394

Number theory Difficulty 5.6 AIME, harder Prove it United States

Problem:
Let SS be the set of ordered pairs (a,b)(a, b) of positive integers such that gcd(a,b)=1\operatorname{gcd}(a, b)=1. Compute
(a,b)S3002a+3b \sum_{(a, b) \in S}\left\lfloor\frac{300}{2 a+3 b}\right\rfloor

Solution

Solution: The key claim is the following.
Claim: The sum in the problem is equal to the number of solutions of 2x+3y3002 x+3 y \leq 300 where x,yx, y are positive integers.

Proof. The sum in the problem is the same as counting the number of triples (a,b,d)(a, b, d) of positive integers such that gcd(a,b)=1\operatorname{gcd}(a, b)=1 and d(2a+3b)300d(2 a+3 b) \leq 300. Now, given such (a,b,d)(a, b, d), we biject it to the pair (x,y)(x, y) described in the claim by x=dax=d a and y=dby=d b. This transformation can be reversed by d=gcd(x,y)d=\operatorname{gcd}(x, y), a=x/da=x / d, and b=y/db=y / d, implying that it is indeed a bijection, so the sum is indeed equal to the number of such (x,y)(x, y).

Hence, we wish to count the number of positive integer solutions to 2x+3y3002 x+3 y \leq 300. One way to do this is via casework on yy, which we know to be an integer less than 100:

- If yy is even, then y=2ky=2 k for 1k491 \leq k \leq 49. Fixing kk, there are exactly 3006k2=1503k\frac{300-6 k}{2}=150-3 k values of xx which satisfy the inequality, hence the number of solutions in this case is
k=149(1503k)=150492=3675 \sum_{k=1}^{49}(150-3 k)=\frac{150 \cdot 49}{2}=3675
- If yy is odd, then y=2k1y=2 k-1 for 1k501 \leq k \leq 50. Fixing yy, there are exactly 3026k2=1513k\frac{302-6 k}{2}=151-3 k values of xx which satisfy the inequality, hence the number of solutions in this case is
k=150(1513k)=149502=3725 \sum_{k=1}^{50}(151-3 k)=\frac{149 \cdot 50}{2}=3725
The final answer is 3675+3725=74003675+3725=7400.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.