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<x≤100,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 y≡−1,y\equiv-1, so x+1x+1 is divisible by y+1y+1 exactly when a≡1(mody+1).a\equiv1\pmod {y+1}. Since x>y,x>y, write a=1+t(y+1)a=1+t(y+1) with t≥1.t\geq1. The bound x≤100x\leq100 becomes t≤⌊100−yy(y+1)⌋.t\leq\left\lfloor\frac{100-y}{y(y+1)}\right\rfloor. Only 1≤y≤91\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