Difference between revisions of "1995 AIME Problems/Problem 8"

Revision as of 19:40, 3 September 2023

Problem

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

Solution 1

Since $y|x$ , $y+1|x+1$ , then $\text{gcd}\,(y,x)=y$ (the bars indicate divisibility) and $\text{gcd}\,(y+1,x+1)=y+1$ . By the Euclidean algorithm, these can be rewritten respectively as $\text{gcd}\,(y,x-y)=y$ and $\text{gcd}\, (y+1,x-y)=y+1$ , which implies that both $y,y+1 | x-y$ . Also, as $\text{gcd}\,(y,y+1) = 1$ , it follows that $y(y+1)|x-y$ . ^[1]

Thus, for a given value of $y$ , we need the number of multiples of $y(y+1)$ from $0$ to $100-y$ (as $x \le 100$ ). It follows that there are $\left\lfloor\frac{100-y}{y(y+1)} \right\rfloor$ satisfactory positive integers for all integers $y \le 100$ . The answer is

$\sum_{y=1}^{99} \left\lfloor\frac{100-y}{y(y+1)} \right\rfloor = 49 + 16 + 8 + 4 + 3 + 2 + 1 + 1 + 1 = \boxed{085}.$

^ Another way of stating this is to note that if $\frac{x}{y}$ and $\frac{x+1}{y+1}$ are integers, then $\frac{x}{y} - 1 = \frac{x-y}{y}$ and $\frac{x+1}{y+1} - 1 = \frac{x-y}{y+1}$ must be integers. Since $y$ and $y+1$ cannot share common prime factors, it follows that $\frac{x-y}{y(y+1)}$ must also be an integer.

Solution 2

We know that $x \equiv 0 \mod y$ and $x+1 \equiv 0 \mod y+1$ .

Write $x$ as $ky$ for some integer $k$ . Then, $ky+1 \equiv 0\mod y+1$ . We can add $k$ to each side in order to factor out a $y+1$ . So, $ky+k+1 \equiv k \mod y+1$ or $k(y+1)+1 \equiv k \mod y+1$ . We know that $k(y+1) \equiv 0 \mod y+1$ . We finally achieve the congruence $1-k \equiv 0 \mod y+1$ .

We can now write $k$ as $(y+1)a+1$ . Plugging this back in, if we have a value for $y$ , then $x = ky = ((y+1)a+1)y = y(y+1)a+y$ . We only have to check values of $y$ when $y(y+1)<100$ . This yields the equations $x = 2a+1, 6a+2, 12a+3, 20a+4, 30a+5, 42a+6, 56a+7, 72a+8, 90a+9$ .

Finding all possible values of $a$ such that $y<x<100$ , we get $49 + 16 + 8 + 4 + 3 + 2 + 1 + 1 + 1 = \boxed{085}.$

Solution 3 (Rigorous, but straightforward)

We use casework: For $y=1$ , we have $3,5,\cdots ,99$ , or $49$ cases. For $y=2$ , we have $8,14,\cdots ,98$ , or $16$ cases. For $y=3$ , we have $15,27,\cdots ,99$ , or $8$ cases. For $y=4$ , we have $24,44\cdots ,84$ , or $4$ cases. For $y=5$ , we have $35,65,95$ , or $3$ cases. For $y=6$ , we have $48,90$ , or $2$ cases. For $y=7$ , we have $63$ , or $1$ case. For $y=8$ , we have $80$ , or $1$ case. For $y=9$ , we have $99$ , or $1$ case.

Adding, we get our final result of $\boxed{085}.$ ~SirAppel

@@ Line 22: / Line 22: @@
 ==Solution 3 (Rigorous, but straightforward)==
 We use casework:
-For <math>y=1</math>, we have <math>x=3,5\cdots ,99</math>, or <math>49</math> cases.
+For <math>y=1</math>, we have <math>3,5,\cdots ,99</math>, or <math>49</math> cases.
-For <math>y=2</math>, we have <math>8,14,\cdots 98</math>, or <math>16</math> cases.
+For <math>y=2</math>, we have <math>8,14,\cdots ,98</math>, or <math>16</math> cases.
-For <math>y=3</math>, we have <math>15,27,\cots 99</math>, or <math>8</math> cases.
+For <math>y=3</math>, we have <math>15,27,\cdots ,99</math>, or <math>8</math> cases.
 For <math>y=4</math>, we have <math>24,44\cdots ,84</math>, or <math>4</math> cases.
 For <math>y=5</math>, we have <math>35,65,95</math>, or <math>3</math> cases.
 For <math>y=6</math>, we have <math>48,90</math>, or <math>2</math> cases.
 For <math>y=7</math>, we have <math>63</math>, or <math>1</math> case.
 For <math>y=8</math>, we have <math>80</math>, or <math>1</math> case.
 For <math>y=9</math>, we have <math>99</math>, or <math>1</math> case.

1995 AIME (Problems • Answer Key • Resources)
Preceded by Problem 7	Followed by Problem 9
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15
All AIME Problems and Solutions

Page

Toolbox

Search