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 "1990 AIME Problems/Problem 1"

(→‎Solution)
(Latex + polishing)
 
(One intermediate revision by one other user not shown)
Line 2: Line 2:
 
The [[increasing sequence]] <math>2,3,5,6,7,10,11,\ldots</math> consists of all [[positive integer]]s that are neither the [[perfect square | square]] nor the [[perfect cube | cube]] of a positive integer. Find the 500th term of this sequence.
 
The [[increasing sequence]] <math>2,3,5,6,7,10,11,\ldots</math> consists of all [[positive integer]]s that are neither the [[perfect square | square]] nor the [[perfect cube | cube]] of a positive integer. Find the 500th term of this sequence.
  
−
== Solution ==
+
== Solution 1==
−
Because there aren't that many perfect squares or cubes, let's look for the smallest perfect square greater than <math>500</math>. This happens to be <math>23^2=529</math>. Notice that there are <math>23</math> squares and <math>8</math> cubes less than or equal to <math>529</math>, but <math>1</math> and <math>2^6</math> are both squares and cubes. Thus, there are <math>529-23-8+2=500</math> numbers in our sequence less than <math>529</math>.  Magically, we want the <math>500th</math> term, so our answer is the smallest non-square and non-cube less than <math>529</math>, which is <math>\boxed{528}</math>.
+
Because there aren't that many perfect squares or cubes, let's look for the smallest perfect square greater than <math>500</math>. This happens to be <math>23^2=529</math>. Notice that there are <math>23</math> squares and <math>8</math> cubes less than or equal to <math>529</math>, but <math>1</math> and <math>2^6</math> are both squares and cubes. Thus, there are <math>529-23-8+2=500</math> numbers in our sequence less than <math>529</math>.  Magically, we want the <math>500th</math> term, so our answer is the biggest non-square and non-cube less than <math>529</math>, which is <math>\boxed{528}</math>.
  
 
== Solution 2==
 
== Solution 2==
−
similar as above, but to get the intuition why we chose to consider 23^2 = 529 , consider this
+
This solution is similar as Solution 1, but to get the intuition why we chose to consider <math>23^2 = 529</math>, consider this:
  
−
we need n - T = 500, where n = #integers in the list 1,2,..,n and T is the set of numbers which are either k^2 or k^3 and <=n
+
We need <math>n - T = 500</math>, where <math>n</math> is an integer greater than 500 and <math>T</math> is the set of numbers which contains all <math>k^2,k^3\le 500</math>.
−
firstly, we clearly need n > 500
+
 
−
so we think of taking the smallest square greater than 500 and let that be equal to n( u could try letting n = 512 = 8^3 to with similiar logic, but quickly realise that it fails). This is done so that set T is easy to calculate
+
Firstly, we clearly need <math>n > 500</math>, so we substitute n for the smallest square or cube greater than <math>500</math>. However, if we use <math>n=8^3=512</math>, the number of terms in <math>T</math> will exceed <math>n-500</math>. Therefore, <math>n=23^2=529</math>, and the number of terms in <math>T</math> is <math>23+8-2=29</math> by the [[Principle of Inclusion-Exclusion]], fulfilling our original requirement of <math>n-T=500</math>.
−
so n = 529, set T = 23+8-2 by PIE hence n-T = 500
+
As a result, our answer is <math>529-1 = \boxed{528}</math>.
−
so our answer is 529-1 = 528
 
  
 
== See also ==
 
== See also ==

Latest revision as of 22:11, 25 June 2023

Problem

The increasing sequence $2,3,5,6,7,10,11,\ldots$ consists of all positive integers that are neither the square nor the cube of a positive integer. Find the 500th term of this sequence.

Solution 1

Because there aren't that many perfect squares or cubes, let's look for the smallest perfect square greater than $500$. This happens to be $23^2=529$. Notice that there are $23$ squares and $8$ cubes less than or equal to $529$, but $1$ and $2^6$ are both squares and cubes. Thus, there are $529-23-8+2=500$ numbers in our sequence less than $529$. Magically, we want the $500th$ term, so our answer is the biggest non-square and non-cube less than $529$, which is $\boxed{528}$.

Solution 2

This solution is similar as Solution 1, but to get the intuition why we chose to consider $23^2 = 529$, consider this:

We need $n - T = 500$, where $n$ is an integer greater than 500 and $T$ is the set of numbers which contains all $k^2,k^3\le 500$.

Firstly, we clearly need $n > 500$, so we substitute n for the smallest square or cube greater than $500$. However, if we use $n=8^3=512$, the number of terms in $T$ will exceed $n-500$. Therefore, $n=23^2=529$, and the number of terms in $T$ is $23+8-2=29$ by the Principle of Inclusion-Exclusion, fulfilling our original requirement of $n-T=500$. As a result, our answer is $529-1 = \boxed{528}$.

See also

1990 AIME (Problems • Answer Key • Resources)
Preceded by
First Question 		Followed by
Problem 2
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=1990_AIME_Problems/Problem_1&oldid=194796"