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 "2008 AIME II Problems/Problem 15"

(solutions by (1) riliu and (2) Altheman)
 
 
(12 intermediate revisions by 9 users not shown)
Line 1: Line 1:
 +
__TOC__
 +
 
== Problem ==
 
== Problem ==
 
Find the largest integer <math>n</math> satisfying the following conditions:
 
Find the largest integer <math>n</math> satisfying the following conditions:
Line 4: Line 6:
 
:(ii) <math>2n + 79</math> is a perfect square.
 
:(ii) <math>2n + 79</math> is a perfect square.
  
−
__TOC__
 
 
== Solution ==
 
== Solution ==
 
=== Solution 1 ===
 
=== Solution 1 ===
−
Write <math>n^2 = (m + 1)^3 - m^3 = 3m^2 + 3m + 1</math>, or equivalently,
+
Write <math>n^2 = (m + 1)^3 - m^3 = 3m^2 + 3m + 1</math>, or equivalently, <math>(2n + 1)(2n - 1) = 4n^2 - 1 = 12m^2 + 12m + 3 = 3(2m + 1)^2</math>.
−
 
 
−
<cmath>(2n + 1)(2n - 1) = 4n^2 - 1 = 12m^2 + 12m + 3 = 3(2m + 1)^2.</cmath>
 
  
 
Since <math>2n + 1</math> and <math>2n - 1</math> are both odd and their difference is <math>2</math>, they are [[relatively prime]]. But since their product is three times a square, one of them must be a square and the other three times a square. We cannot have <math>2n - 1</math> be three times a square, for then <math>2n + 1</math> would be a square congruent to <math>2</math> modulo <math>3</math>, which is impossible.
 
Since <math>2n + 1</math> and <math>2n - 1</math> are both odd and their difference is <math>2</math>, they are [[relatively prime]]. But since their product is three times a square, one of them must be a square and the other three times a square. We cannot have <math>2n - 1</math> be three times a square, for then <math>2n + 1</math> would be a square congruent to <math>2</math> modulo <math>3</math>, which is impossible.
Line 15: Line 14:
 
Thus <math>2n - 1</math> is a square, say <math>b^2</math>. But <math>2n + 79</math> is also a square, say <math>a^2</math>. Then <math>(a + b)(a - b) = a^2 - b^2 = 80</math>. Since <math>a + b</math> and <math>a - b</math> have the same parity and their product is even, they are both even. To maximize <math>n</math>, it suffices to maximize <math>2b = (a + b) - (a - b)</math> and check that this yields an integral value for <math>m</math>. This occurs when <math>a + b = 40</math> and <math>a - b = 2</math>, that is, when <math>a = 21</math> and <math>b = 19</math>. This yields <math>n = 181</math> and <math>m = 104</math>, so the answer is <math>\boxed{181}</math>.
 
Thus <math>2n - 1</math> is a square, say <math>b^2</math>. But <math>2n + 79</math> is also a square, say <math>a^2</math>. Then <math>(a + b)(a - b) = a^2 - b^2 = 80</math>. Since <math>a + b</math> and <math>a - b</math> have the same parity and their product is even, they are both even. To maximize <math>n</math>, it suffices to maximize <math>2b = (a + b) - (a - b)</math> and check that this yields an integral value for <math>m</math>. This occurs when <math>a + b = 40</math> and <math>a - b = 2</math>, that is, when <math>a = 21</math> and <math>b = 19</math>. This yields <math>n = 181</math> and <math>m = 104</math>, so the answer is <math>\boxed{181}</math>.
  
−
__TOC__
 
 
=== Solution 2 ===
 
=== Solution 2 ===
−
Suppose that the consecutive squares are <math>m</math> and <math>m + 1</math>. We can use completing the square and the first condition to get:
+
Suppose that the consecutive cubes are <math>m</math> and <math>m + 1</math>. We can use completing the square and the first condition to get:
 
<cmath>
 
<cmath>
 
(2n)^2 - 3(2m + 1)^2 = 1\equiv a^2 - 3b^2
 
(2n)^2 - 3(2m + 1)^2 = 1\equiv a^2 - 3b^2
 
</cmath>
 
</cmath>
−
where <math>a</math> and <math>b</math> are non-negative integers. Now this is a [[pell equation]], with solutions in the form <math>(2 + \sqrt {3})^k = a_k + \sqrt {3}b_k,</math> <math>k = 0,1,2,3,...</math>. However, <math>a</math> is even and <math>b</math> is odd. It is easy to see that the parity of <math>a</math> and <math>b</math> switch each time (by induction). Hence all solutions to the first condition are in the form:
+
where <math>a</math> and <math>b</math> are non-negative integers. Now this is a [[Pell equation]], with solutions in the form <math>(2 + \sqrt {3})^k = a_k + \sqrt {3}b_k,</math> <math>k = 0,1,2,3,...</math>. However, <math>a</math> is even and <math>b</math> is odd. It is easy to see that the parity of <math>a</math> and <math>b</math> switch each time (by induction). Hence all solutions to the first condition are in the form:
 
<cmath>
 
<cmath>
 
(2 + \sqrt {3})^{2k + 1} = a_k + \sqrt {3}b_k
 
(2 + \sqrt {3})^{2k + 1} = a_k + \sqrt {3}b_k
 
</cmath>
 
</cmath>
−
where <math>k = 0,1,2,..</math>. So we can (with very little effort) obtain the following: <math>(k,a_k = 2n) = (0,2),(1,26),(2,362),(3,5042)</math>. It is an AIME problem so it is implicit that <math>n < 1000</math>, so <math>2n < 2000</math>. It is easy to see that <math>a_n</math> is strictly increasing by induction. Checking <math>2n = 362\implies n = 181</math> in the second condition works (we know <math>b_k</math> is odd so we don't need to find <math>m</math>). So we're done.
+
where <math>k = 0,1,2,..</math>. So we can (with very little effort) obtain the following: <math>(k,a_k = 2n) = (0,2),(1,26),(2,362),(3,5042)</math>. It is an AIME problem so it is implicit that <math>n < 1000</math>, so <math>2n < 2000</math>. It is easy to see that <math>a_n</math> is strictly increasing by induction. Checking <math>2n = 362\implies n =\boxed{181}</math> in the second condition works (we know <math>b_k</math> is odd so we don't need to find <math>m</math>). So we're done.
 +
 
 +
=== Solution 3 (Big Bash) ===
 +
 
 +
Let us generate numbers <math>1</math> to <math>1000</math> for the second condition, for squares. We know for <math>N</math> to be integer, the squares must be odd. So we generate <math>N = 1, 21, 45, 73, 105, 141, 181, 381, 441, 721, 801</math>. <math>N</math> cannot exceed <math>1000</math> since it is AIME problem. Now take the first criterion, let <math>a</math> be the smaller consecutive cube. We then get:
 +
 
 +
<math> N^2 = (A + 1)^3 - A^3</math>
 +
 
 +
<math> N^2 - 1 = 3A^2 + 3A</math>
 +
 
 +
<math> (N + 1)(N - 1) = 3A(A + 1)</math>
 +
 
 +
Now we know either <math>N + 1</math> or <math>N - 1</math> must be factor of <math>3</math>, hence <math>N = 1 \pmod 3 </math> or<math>  N = 2 \pmod 3</math>. Only <math>1, 73, 181, 721</math> satisfy this criterion. Testing each of the numbers in the condition yields <math>181</math> as the largest that fits both, thus answer <math>= \boxed{181}</math>.
  
 
== See also ==
 
== See also ==
Line 31: Line 41:
  
 
[[Category:Intermediate Number Theory Problems]]
 
[[Category:Intermediate Number Theory Problems]]
 +
{{MAA Notice}}

Latest revision as of 15:23, 2 January 2024

Problem

Find the largest integer $n$ satisfying the following conditions:

(i) $n^2$ can be expressed as the difference of two consecutive cubes;
(ii) $2n + 79$ is a perfect square.

Solution

Solution 1

Write $n^2 = (m + 1)^3 - m^3 = 3m^2 + 3m + 1$, or equivalently, $(2n + 1)(2n - 1) = 4n^2 - 1 = 12m^2 + 12m + 3 = 3(2m + 1)^2$.

Since $2n + 1$ and $2n - 1$ are both odd and their difference is $2$, they are relatively prime. But since their product is three times a square, one of them must be a square and the other three times a square. We cannot have $2n - 1$ be three times a square, for then $2n + 1$ would be a square congruent to $2$ modulo $3$, which is impossible.

Thus $2n - 1$ is a square, say $b^2$. But $2n + 79$ is also a square, say $a^2$. Then $(a + b)(a - b) = a^2 - b^2 = 80$. Since $a + b$ and $a - b$ have the same parity and their product is even, they are both even. To maximize $n$, it suffices to maximize $2b = (a + b) - (a - b)$ and check that this yields an integral value for $m$. This occurs when $a + b = 40$ and $a - b = 2$, that is, when $a = 21$ and $b = 19$. This yields $n = 181$ and $m = 104$, so the answer is $\boxed{181}$.

Solution 2

Suppose that the consecutive cubes are $m$ and $m + 1$. We can use completing the square and the first condition to get: \[(2n)^2 - 3(2m + 1)^2 = 1\equiv a^2 - 3b^2\] where $a$ and $b$ are non-negative integers. Now this is a Pell equation, with solutions in the form $(2 + \sqrt {3})^k = a_k + \sqrt {3}b_k,$ $k = 0,1,2,3,...$. However, $a$ is even and $b$ is odd. It is easy to see that the parity of $a$ and $b$ switch each time (by induction). Hence all solutions to the first condition are in the form: \[(2 + \sqrt {3})^{2k + 1} = a_k + \sqrt {3}b_k\] where $k = 0,1,2,..$. So we can (with very little effort) obtain the following: $(k,a_k = 2n) = (0,2),(1,26),(2,362),(3,5042)$. It is an AIME problem so it is implicit that $n < 1000$, so $2n < 2000$. It is easy to see that $a_n$ is strictly increasing by induction. Checking $2n = 362\implies n =\boxed{181}$ in the second condition works (we know $b_k$ is odd so we don't need to find $m$). So we're done.

Solution 3 (Big Bash)

Let us generate numbers $1$ to $1000$ for the second condition, for squares. We know for $N$ to be integer, the squares must be odd. So we generate $N = 1, 21, 45, 73, 105, 141, 181, 381, 441, 721, 801$. $N$ cannot exceed $1000$ since it is AIME problem. Now take the first criterion, let $a$ be the smaller consecutive cube. We then get:

$N^2 = (A + 1)^3 - A^3$

$N^2 - 1 = 3A^2 + 3A$

$(N + 1)(N - 1) = 3A(A + 1)$

Now we know either $N + 1$ or $N - 1$ must be factor of $3$, hence $N = 1 \pmod 3$ or$N = 2 \pmod 3$. Only $1, 73, 181, 721$ satisfy this criterion. Testing each of the numbers in the condition yields $181$ as the largest that fits both, thus answer $= \boxed{181}$.

See also

2008 AIME II (Problems • Answer Key • Resources)
Preceded by
Problem 14 		Followed by
Last problem
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=2008_AIME_II_Problems/Problem_15&oldid=209570"