InclusionExclusion AIME Intermediate
2014


Problem - 85

Find the number of rational numbers $r$, $0 < r < 1$, such that when $r$ is written as a fraction in lowest terms, the numerator and the denominator have a sum of $1000$.


Let $r=\frac{d}{1000-d}$ where $1\le d < 500$. This expression is reducible if and only if $d$ and $(1000-d)$ are not co-prime. Because $1000=2^3\times 5^3$, therefore $d$ has to be a multiple of $2$ or $5$ in order for these two numbers are not co-prime. Hence, this problem can be solved using the inclusion-exclusion principle. The answer is then $$499 - \left(\left\lfloor{\frac{499}{2}}\right\rfloor+\left\lfloor{\frac{499}{5}}\right\rfloor-\left\lfloor{\frac{499}{10}}\right\rfloor\right)=\boxed{200}$$

report an error