Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

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

m (outline)
(→‎Solution 3 (Rigorous, but straightforward))
 
(9 intermediate revisions by 6 users not shown)
Line 1: Line 1:
 
== Problem ==
 
== Problem ==
−
For how many ordered pairs of positive integers <math>(x,y),</math> with <math>y<x\le 100,</math> are both <math>\frac xy</math> and <math>\frac{x+1}{y+1}</math> integers?
+
For how many ordered pairs of positive [[integer]]s <math>(x,y),</math> with <math>y<x\le 100,</math> are both <math>\frac xy</math> and <math>\frac{x+1}{y+1}</math> integers?
  
−
== Solution ==
+
== Solution 1==
−
Since <math>y|x</math>, <math>y+1|x+1</math>, then <math>\text{gcd}\,(y,x)=y</math> and <math>\text{gcd}\,(y+1,x+1)=y+1</math>. By the [[Euclidean Algorithm]], these can be rewritten as <math>\text{gcd}\,(y,x-y)=y</math> and <math>\text{gcd}\, (y+1,x-y)=y+1</math>, which implies that <math>y,y+1 | x-y</math>. Also, <math>\text{gcd}\,(y,y+1) = 1</math>, so <math>\frac{x-y}{y(y+1)}</math> must be an integer. Substituting the upper bound of <math>x \le 100</math>, it follows that there are <math>\left\lfloor\frac{100-y}{y(y+1)} \right\rfloor</math> satisfactory positive integers. The answer is  
+
Since <math>y|x</math>, <math>y+1|x+1</math>, then <math>\text{gcd}\,(y,x)=y</math> (the bars indicate [[divisibility]]) and <math>\text{gcd}\,(y+1,x+1)=y+1</math>. By the [[Euclidean algorithm]], these can be rewritten respectively as <math>\text{gcd}\,(y,x-y)=y</math> and <math>\text{gcd}\, (y+1,x-y)=y+1</math>, which implies that both <math>y,y+1 | x-y</math>. Also, as <math>\text{gcd}\,(y,y+1) = 1</math>, it follows that <math>y(y+1)|x-y</math>. {{ref|1}}
−
<cmath>\sum_{y=1}^{99} \left\lfloor\frac{100-y}{y(y+1)} \right\rfloor = \boxed{085}</cmath>
+
 
 +
Thus, for a given value of <math>y</math>, we need the number of multiples of <math>y(y+1)</math> from <math>0</math> to <math>100-y</math> (as <math>x \le 100</math>). It follows that there are <math>\left\lfloor\frac{100-y}{y(y+1)} \right\rfloor</math> satisfactory positive integers for all integers <math>y \le 100</math>. The answer is  
 +
 
 +
<cmath>\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}.</cmath>
 +
 
 +
<br /><br />{{note|1}} Another way of stating this is to note that if <math>\frac{x}{y}</math> and <math>\frac{x+1}{y+1}</math> are integers, then <math>\frac{x}{y} - 1 = \frac{x-y}{y}</math> and <math>\frac{x+1}{y+1} - 1 = \frac{x-y}{y+1}</math> must be integers. Since <math>y</math> and <math>y+1</math> cannot share common prime factors, it follows that <math>\frac{x-y}{y(y+1)}</math> must also be an integer.
 +
 
 +
== Solution 2==
 +
We know that <math>x \equiv 0 \mod y</math> and  <math>x+1 \equiv 0 \mod y+1</math>.
 +
 
 +
Write <math>x</math> as <math>ky</math> for some integer <math>k</math>. Then, <math>ky+1 \equiv 0\mod y+1</math>. We can add <math>k</math> to each side in order to factor out a <math>y+1</math>. So, <math>ky+k+1 \equiv k \mod y+1</math> or <math>k(y+1)+1 \equiv k \mod y+1</math>. We know that <math>k(y+1) \equiv 0 \mod y+1</math>. We finally achieve the congruence <math>1-k \equiv 0 \mod y+1</math>.
 +
 
 +
We can now write <math>k</math> as <math>(y+1)a+1</math>. Plugging this back in, if we have a value for <math>y</math>, then <math>x = ky = ((y+1)a+1)y = y(y+1)a+y</math>. We only have to check values of <math>y</math> when <math>y(y+1)<100</math>. This yields the equations <math>x = 2a+1, 6a+2, 12a+3, 20a+4, 30a+5, 42a+6, 56a+7, 72a+8, 90a+9</math>.
 +
 
 +
Finding all possible values of <math>a</math> such that <math>y<x<100</math>, we get <math>49 + 16 + 8 + 4 + 3 + 2 + 1 + 1 + 1 = \boxed{085}.</math>
 +
 
 +
==Solution 3 (Rigorous, but straightforward)==
 +
We use casework:
 +
 
 +
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=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.
 +
 
 +
Adding, we get our final result of <math>\boxed{085}.</math>
 +
 
 +
Note: In general, all of the solutions for all <math>y</math> are <math>y+by(y+1)</math>, for any <math>b</math> such that <math>y+by(y+1)=x<100</math>
 +
 
 +
~SirAppel
 +
 
 +
Also, note that <math>n+1</math> just starts with <math>(y+1)^2</math>, and adds <math>y(y+1)</math> until it is greater than <math>100</math>.
 +
 
 +
~Yiyj1
  
 
== See also ==
 
== See also ==
 
{{AIME box|year=1995|num-b=7|num-a=9}}
 
{{AIME box|year=1995|num-b=7|num-a=9}}
 +
 +
[[Category:Intermediate Number Theory Problems]]
 +
{{MAA Notice}}

Latest revision as of 16:37, 1 January 2024

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}.$

Note: In general, all of the solutions for all $y$ are $y+by(y+1)$, for any $b$ such that $y+by(y+1)=x<100$

~SirAppel

Also, note that $n+1$ just starts with $(y+1)^2$, and adds $y(y+1)$ until it is greater than $100$.

~Yiyj1

See also

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

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=1995_AIME_Problems/Problem_8&oldid=209407"