1995 AIME Problem 8

Attempt Problem 8 of the 1995 AIME below, then check your answer against the professionally curated solution from LIVE by Po-Shen Loh. You can also try the full timed exam, view all 1995 AIME solutions, or check the answer key.

All problems are used with official legal permission of the Mathematical Association of America (MAA).

8.

For how many ordered pairs of positive integers (x,y),(x,y), with y<x100,y<x\leq100, are both xy\frac{x}{y} and x+1y+1\frac{x+1}{y+1} integers?

Answer: 85
Concepts:divisibilityfloor and ceiling functionscounting pairs
Difficulty rating: 2060
Small Hint:

Write x=ayx=ay and reduce x+1x+1 modulo y+1y+1

Big Hint:

The quotient aa must have the form 1+t(y+1)1+t(y+1); count the possible positive values of tt

Solution:

Write x=ay.x=ay. Modulo y+1,y+1, we have y1,y\equiv-1, so x+1x+1 is divisible by y+1y+1 exactly when a1(mody+1).a\equiv1\pmod {y+1}. Since x>y,x>y, write a=1+t(y+1)a=1+t(y+1) with t1.t\geq1. The bound x100x\leq100 becomes t100yy(y+1).t\leq\left\lfloor\frac{100-y}{y(y+1)}\right\rfloor. Only 1y91\leq y\leq9 contribute, giving 49+16+8+4+3+2+1+1+1=85.\begin{aligned}49+16+8&+4+3\\&+2+1+1+1\\&=85.\end{aligned}

← Problem 7#7
Full Exam

Problem 8 in Other Years