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 "1998 AIME Problems/Problem 2"

m (→‎Solution 1: extra space?)
(→‎Solution 4 - Unrigorous engineers induction solution)
 
(7 intermediate revisions by 4 users not shown)
Line 1: Line 1:
 
== Problem ==
 
== Problem ==
−
Find the number of [[ordered pair]]s <math>\displaystyle (x,y)</math> of positive integers that satisfy <math>x \le 2y \le 60 \displaystyle</math> and <math>\displaystyle y \le 2x \le 60</math>.
+
Find the number of [[ordered pair]]s <math>(x,y)</math> of positive integers that satisfy <math>x \le 2y \le 60</math> and <math>y \le 2x \le 60</math>.
 
__TOC__
 
__TOC__
 
== Solution ==
 
== Solution ==
Line 8: Line 8:
 
<div style="text-align:center;"><math>A = I + \frac B2 - 1</math></div>
 
<div style="text-align:center;"><math>A = I + \frac B2 - 1</math></div>
  
−
The conditions give us four [[inequality|inequalities]]: <math>x \le 30 \displaystyle</math>, <math>y \displaystyle \le 30</math>, <math>\displaystyle x \le 2y</math>, <math>\displaystyle y \le 2x</math>. These create a [[quadrilateral]], whose area is <math>\frac 12</math> of the 30 by 30 [[square]] it is in. A simple way to see this is to note that the two triangles outside of the quadrilateral form half of the area of the 30 by 30 square.
+
The conditions give us four [[inequality|inequalities]]: <math>x \le 30</math>, <math>y\le 30</math>, <math>x \le 2y</math>, <math>y \le 2x</math>. These create a [[quadrilateral]], whose area is <math>\frac 12</math> of the 30 by 30 [[square]] it is in. A simple way to see this is to note that the two triangles outside of the quadrilateral form half of the area of the 30 by 30 square.
  
−
So <math>A = \frac 12 \cdot 30^2 = 450</math>. <math>\displaystyle B</math> we can calculate by just counting. Ignoring the vertices, the top and right sides have 14 [[lattice point]]s, and the two diagonals each have 14 lattice points (for the top diagonal, every value of <math>x</math> corresponds with an integer value of <math>y</math> as <math>y = 2x</math> and vice versa for the bottom, so and there are 14 values for x not counting vertices). Adding the four vertices, there are 60 points on the borders.
+
So <math>A = \frac 12 \cdot 30^2 = 450</math>. <math>B</math> we can calculate by just counting. Ignoring the vertices, the top and right sides have 14 [[lattice point]]s, and the two diagonals each have 14 lattice points (for the top diagonal, every value of <math>x</math> corresponds with an integer value of <math>y</math> as <math>y = 2x</math> and vice versa for the bottom, so and there are 14 values for x not counting vertices). Adding the four vertices, there are 60 points on the borders.
  
−
<div style="text-align:center;"><math>450 = I + \frac {60}2 - 1 \displaystyle</math><br /><math>\displaystyle I = 421</math></div>
+
<div style="text-align:center;"><math>450 = I + \frac {60}2 - 1</math><br /><math>I = 421</math></div>
  
 
Since the inequalities also include the equals case, we include the boundaries, which gives us <math>421 + 60 = 481</math> ordered pairs. However, the question asks us for positive integers, so <math>(0,0)</math> doesn't count; hence, the answer is <math>480</math>.
 
Since the inequalities also include the equals case, we include the boundaries, which gives us <math>421 + 60 = 481</math> ordered pairs. However, the question asks us for positive integers, so <math>(0,0)</math> doesn't count; hence, the answer is <math>480</math>.
  
 
=== Solution 2 ===
 
=== Solution 2 ===
−
First, note that all pairs of the form <math>\displaystyle (a,a)</math>, <math>1\le a \displaystyle \le30</math> work.
+
First, note that all pairs of the form <math>(a,a)</math>, <math>1\le a\le30</math> work.
  
−
Now, considered the ordered pairs with <math>x < y</math>, so that <math>x < 2y</math> is automatically satisfied. Since <math>x < y\le 2x</math>, there are <math>2x - x = x \displaystyle</math> possible values of <math>y</math>. Hence, given <math>x</math>, there are <math>x</math> values of possible <math>y</math> for which <math>x < y</math> and the above conditions are satisfied. But <math>2y \displaystyle \le60</math>, so this only works for <math>x\le15</math>. Thus, there are
+
Now, considered the ordered pairs with <math>x < y</math>, so that <math>x < 2y</math> is automatically satisfied. Since <math>x < y\le 2x</math>, there are <math>2x - x = x</math> possible values of <math>y</math>. Hence, given <math>x</math>, there are <math>x</math> values of possible <math>y</math> for which <math>x < y</math> and the above conditions are satisfied. But <math>2y\le60</math>, so this only works for <math>x\le15</math>. Thus, there are
  
−
<math>\sum_{i=1}^{15} i=\frac{(30)(31)}{2}</math>
+
<math>\sum_{i=1}^{15} i=\frac{(15)(16)}{2}</math>
  
−
ordered pairs. For <math>x > 15</math>, <math>y</math> must follow <math>x < y\le 30 \displaystyle</math>. Hence, there are <math>30 - x</math> possibilities for <math>y</math>, and there are
+
ordered pairs. For <math>x > 15</math>, <math>y</math> must follow <math>x < y\le 30</math>. Hence, there are <math>30 - x</math> possibilities for <math>y</math>, and there are
  
 
<math>\sum_{i=16}^{30}(30-i)=\sum_{i=0}^{14}i=\frac{(14)(15)}{2}</math>
 
<math>\sum_{i=16}^{30}(30-i)=\sum_{i=0}^{14}i=\frac{(14)(15)}{2}</math>
Line 29: Line 29:
 
ordered pairs.
 
ordered pairs.
  
−
By symmetry, there are also <math>\displaystyle \frac {(15)(16)}{2} + \frac {(14)(15)}{2}</math> ordered pairs with <math>x > y</math> and the above criteria satisfied.
+
By symmetry, there are also <math>\frac {(15)(16)}{2} + \frac {(14)(15)}{2}</math> ordered pairs with <math>x > y</math> and the above criteria satisfied.
  
 
Hence, the total is
 
Hence, the total is
  
 
<math>\frac{(15)(16)}{2}+\frac{(14)(15)}{2}+\frac{(15)(16)}{2}+\frac{(14)(15)}{2}+30=480.</math>
 
<math>\frac{(15)(16)}{2}+\frac{(14)(15)}{2}+\frac{(15)(16)}{2}+\frac{(14)(15)}{2}+30=480.</math>
 +
 +
=== Solution 3 ===
 +
<math> y\le2x\le60</math>
 +
 +
Multiplying both sides by 2 yields:
 +
 +
<math> 2y\le4x\le120</math>
 +
 +
Then the two inequalities can be merged to form the following inequality:
 +
 +
<math> x\le2y\le4x\le120</math>
 +
 +
Additionally, we must ensure that <math>2y<60</math>
 +
 +
Therefore we must find pairs <math>(x,y)</math> that satisfy the inequality above.
 +
A bit of trial and error and observing patterns leads to the answer <math>480</math>.
 +
 +
It should be noted that the cases for <math>x\le15</math> and <math>x>15</math> should be considered separately in order to ensure that <math>2y < 60</math>.
 +
 +
===Solution 4 - Unrigorous engineers induction solution===
 +
 +
We will try out small cases.
 +
 +
By replacing 60 in this problem with 2, we count only 1 ordered pair. By doing with 4, we count 4 ordered pairs. With 6, we get 7 pairs. With 8 we get 12. By continuing on, and then finding the difference between adjacent terms (1,3,3,5,5,...). We suspect that if 60 was replaced with 2n, we will find 1+3+3+5+5+7+7 ...., where there will be n terms. Thus, our answer is 1+3+3+5+5.... 29+29+31 = 16*30 = 480.
 +
 +
-Alexlikemath
 +
 +
 +
===Solution 5 - Counting Head on===
 +
 +
Notice <math>x</math> and <math>y</math> both must be equal or less than 30. The inequalities given have no complicated qualities. We can recompile them by understanding: Two times the larger integer will also be larger than the smaller integer; Two times the smaller integer is greater or equal to the greater integer if and only if the greater integer is less or equal to the double of the smaller integer. Knowing this, we create a chart. We will first solve without order, then multiply pairs by 2 at the end. <math>x</math> can be 1-30, so we'll start with 1. The only possible value for <math>y</math> is 1. For <math>x = 2</math>, <math>y</math> can be 2-4. For <math>x = 3</math>, <math>y</math> can be 3-6. There is an obvious pattern here. For every integer after 1, the possible values for <math>y</math> will be numbers <math>x</math>-<math>2x</math>. This predictably ends at <math>x = 15</math> because <math>y</math> will reach 30. When <math>x = 16</math>, then the number of possible values of <math>y</math> will begin to drop again, equaling the amount when <math>x = 14</math>. Then when we finally sum the group together, for <math>x = 2</math> to <math>x = 14</math> there are 104 pairs with 2 distinct values, and 13 values with congruent values. These will not be multiplied by 2 later on. <math>x = 16</math> to <math>x = 28</math> gives the same amount. Then <math>x = 15</math> and <math>x = 29</math> gives 16 and 2 values respectively, with two congruent values each. Finally, <math>x = 1</math> and <math>x = 30</math> give 3 and 1 respectively.
 +
 +
Sum them together and you will get 480.
 +
 +
 +
-jackshi2006
  
 
== See also ==
 
== See also ==
Line 39: Line 75:
  
 
[[Category:Intermediate Geometry Problems]]
 
[[Category:Intermediate Geometry Problems]]
 +
{{MAA Notice}}

Latest revision as of 15:34, 6 August 2020

Problem

Find the number of ordered pairs $(x,y)$ of positive integers that satisfy $x \le 2y \le 60$ and $y \le 2x \le 60$.

Solution

Solution 1

AIME 1998-2.png

Pick's theorem states that:

$A = I + \frac B2 - 1$

The conditions give us four inequalities: $x \le 30$, $y\le 30$, $x \le 2y$, $y \le 2x$. These create a quadrilateral, whose area is $\frac 12$ of the 30 by 30 square it is in. A simple way to see this is to note that the two triangles outside of the quadrilateral form half of the area of the 30 by 30 square.

So $A = \frac 12 \cdot 30^2 = 450$. $B$ we can calculate by just counting. Ignoring the vertices, the top and right sides have 14 lattice points, and the two diagonals each have 14 lattice points (for the top diagonal, every value of $x$ corresponds with an integer value of $y$ as $y = 2x$ and vice versa for the bottom, so and there are 14 values for x not counting vertices). Adding the four vertices, there are 60 points on the borders.

$450 = I + \frac {60}2 - 1$
$I = 421$

Since the inequalities also include the equals case, we include the boundaries, which gives us $421 + 60 = 481$ ordered pairs. However, the question asks us for positive integers, so $(0,0)$ doesn't count; hence, the answer is $480$.

Solution 2

First, note that all pairs of the form $(a,a)$, $1\le a\le30$ work.

Now, considered the ordered pairs with $x < y$, so that $x < 2y$ is automatically satisfied. Since $x < y\le 2x$, there are $2x - x = x$ possible values of $y$. Hence, given $x$, there are $x$ values of possible $y$ for which $x < y$ and the above conditions are satisfied. But $2y\le60$, so this only works for $x\le15$. Thus, there are

$\sum_{i=1}^{15} i=\frac{(15)(16)}{2}$

ordered pairs. For $x > 15$, $y$ must follow $x < y\le 30$. Hence, there are $30 - x$ possibilities for $y$, and there are

$\sum_{i=16}^{30}(30-i)=\sum_{i=0}^{14}i=\frac{(14)(15)}{2}$

ordered pairs.

By symmetry, there are also $\frac {(15)(16)}{2} + \frac {(14)(15)}{2}$ ordered pairs with $x > y$ and the above criteria satisfied.

Hence, the total is

$\frac{(15)(16)}{2}+\frac{(14)(15)}{2}+\frac{(15)(16)}{2}+\frac{(14)(15)}{2}+30=480.$

Solution 3

$y\le2x\le60$

Multiplying both sides by 2 yields:

$2y\le4x\le120$

Then the two inequalities can be merged to form the following inequality:

$x\le2y\le4x\le120$

Additionally, we must ensure that $2y<60$

Therefore we must find pairs $(x,y)$ that satisfy the inequality above. A bit of trial and error and observing patterns leads to the answer $480$.

It should be noted that the cases for $x\le15$ and $x>15$ should be considered separately in order to ensure that $2y < 60$.

Solution 4 - Unrigorous engineers induction solution

We will try out small cases.

By replacing 60 in this problem with 2, we count only 1 ordered pair. By doing with 4, we count 4 ordered pairs. With 6, we get 7 pairs. With 8 we get 12. By continuing on, and then finding the difference between adjacent terms (1,3,3,5,5,...). We suspect that if 60 was replaced with 2n, we will find 1+3+3+5+5+7+7 ...., where there will be n terms. Thus, our answer is 1+3+3+5+5.... 29+29+31 = 16*30 = 480.

-Alexlikemath


Solution 5 - Counting Head on

Notice $x$ and $y$ both must be equal or less than 30. The inequalities given have no complicated qualities. We can recompile them by understanding: Two times the larger integer will also be larger than the smaller integer; Two times the smaller integer is greater or equal to the greater integer if and only if the greater integer is less or equal to the double of the smaller integer. Knowing this, we create a chart. We will first solve without order, then multiply pairs by 2 at the end. $x$ can be 1-30, so we'll start with 1. The only possible value for $y$ is 1. For $x = 2$, $y$ can be 2-4. For $x = 3$, $y$ can be 3-6. There is an obvious pattern here. For every integer after 1, the possible values for $y$ will be numbers $x$-$2x$. This predictably ends at $x = 15$ because $y$ will reach 30. When $x = 16$, then the number of possible values of $y$ will begin to drop again, equaling the amount when $x = 14$. Then when we finally sum the group together, for $x = 2$ to $x = 14$ there are 104 pairs with 2 distinct values, and 13 values with congruent values. These will not be multiplied by 2 later on. $x = 16$ to $x = 28$ gives the same amount. Then $x = 15$ and $x = 29$ gives 16 and 2 values respectively, with two congruent values each. Finally, $x = 1$ and $x = 30$ give 3 and 1 respectively.

Sum them together and you will get 480.


-jackshi2006

See also

1998 AIME (Problems • Answer Key • Resources)
Preceded by
Problem 1 		Followed by
Problem 3
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=1998_AIME_Problems/Problem_2&oldid=130844"