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

1998 AIME Problems/Problem 2

Revision as of 16:31, 7 September 2007 by Azjps (talk | contribs) (prob/sol, sol2 by towersfreak2006)

Problem

Find the number of ordered pairs $\displaystyle (x,y)$ of positive integers that satisfy $x \le 2y \le 60 \displaystyle$ and $\displaystyle 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 \displaystyle$, $y \displaystyle \le 30$, $\displaystyle x \le 2y$, $\displaystyle 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$. $\displaystyle 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 \displaystyle$


$\displaystyle 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 $\displaystyle (a,a)$, $1\le a \displaystyle \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 \displaystyle$ 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 \displaystyle \le60$, so this only works for $x\le15$. Thus, there are

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

ordered pairs. For $x > 15$, $y$ must follow $x < y\le 30 \displaystyle$. 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 $\displaystyle \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.$

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
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=1998_AIME_Problems/Problem_2&oldid=15847"