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 "2010 USAJMO Problems/Problem 4"

(→‎Problem)
(→‎Solution 4)
 
(9 intermediate revisions by 6 users not shown)
Line 47: Line 47:
  
 
==Solution 2==
 
==Solution 2==
−
We proceed via induction on n. Notice that we prove instead a stronger result: there exists a parabolic triangle with area <math>2^nm</math> with two of the vertices sharing the same ordinate (y-coordinate).
+
We proceed via induction on n. Notice that we prove instead a stronger result: there exists a parabolic triangle with area <math>(2^nm)^2</math> with two of the vertices sharing the same y-coordinate.
  
−
Base case:
+
BASE CASE:
−
If n = 0, consider the parabolic triangle ABC with A(0, 0), B(1, 1), C(-1, 1) that has area 1/2 * 1 * 2 = 1, so that m = 1.
+
If <math>n = 0</math>, consider the parabolic triangle <math>ABC</math> with <math>A(0, 0), B(1, 1), C(-1, 1)</math> that has area <math>1/2 \cdot 1 \cdot 2 = 1</math>, so that <math>n = 0</math> and <math>m = 1</math>.
−
If n = 1, let ABC = A(1, 1), B(2, 4), C(-2, 4). Because ABC has area 1/2 * 3 * 4 = 6, we set n = 1 and m = 3.
+
If <math>n = 1</math>, let <math>ABC = A(5, 25), B(4, 16), C(-4, 16)</math>. Because <math>ABC</math> has area <math>1/2 \cdot 8 \cdot 9 = 36</math>, we set <math>n = 1</math> and <math>m = 3</math>.
−
If n = 2, consider the triangle formed by A(3, 9), B(4, 16), C(-4, 16). It is parabolic and has area 1/2 * 7 * 8 = 28, so n = 2 and m = 7.
+
If <math>n = 2</math>, consider the triangle formed by <math>A(21, 441), B(3, 9), C(-3, 9)</math>. It is parabolic and has area <math>1/2 \cdot 6 \cdot 432 = 1296 = 36^2</math>, so <math>n = 2</math> and <math>m = 9</math>.
  
−
Inductive step:
+
INDUCTIVE STEP:
−
If n = k produces parabolic triangle ABC with A(a, <math>a^2</math>), B(b, <math>b^2</math>), and C(-b, <math>b^2</math>), consider A'B'C' with vertices A(2a, <math>4a^2</math>), B(2b, <math>4b^2</math>), and C(-2b, <math>4b^2</math>). If ABC has area <math>2^km</math>, then A'B'C' has area <math>2^{k+3}m</math>, which is easily verified using the 1/2 * base * height formula for triangle area. This completes the inductive step for k -> k+3.
+
If <math>n = k</math> produces parabolic triangle <math>ABC</math> with <math>A(a, a^2), B(b, b^2),</math> and <math>C(-b, b^2)</math>, consider <math>A</math>'<math>B</math>'<math>C</math>' with vertices <math>A(4a, 16a^2)</math>, <math>B(4b, 16b^2)</math>, and <math>C(-4b, 16b^2)</math>. If <math>ABC</math> has area <math>(2^km)^2</math>, then <math>A</math>'<math>B</math>'<math>C</math>' has area <math>(2^{k+3}m)^2</math>, which is easily verified using the <math>1/2 \cdot\text{base} \cdot \text{height}</math> formula for triangle area. This completes the inductive step for <math>k \implies k+3</math>.
  
−
Hence, for every nonnegative integer n, there exists an odd m and a parabolic triangle with area <math>2^nm</math> with two vertices sharing the same ordinate. The problem statement is a direct result of this result.
+
Hence, for every nonnegative integer <math>n</math>, there exists an odd <math>m</math> and a parabolic triangle with area <math>(2^nm)^2</math> with two vertices sharing the same ordinate. The problem statement is a direct result of this result.         -MathGenius_
 +
 
 +
==Solution 3 (without induction)==
 +
First, consider triangle with vertices <math>(0,0)</math>, <math>(1,1)</math>, <math>(-1,1)</math>. This has area <math>1</math> so <math>n=0</math> case is satisfied.
 +
 
 +
Then, consider triangle with vertices <math>(a,a^2), (-a,a^2), (b,b^2)</math>, and set <math>a=2^{2n}</math> and <math>b=2^{4n-2}+1</math>.
 +
The area of this triangle is <math>\frac{1}{2} \cdot base \cdot height=a(b^2-a^2)</math>.
 +
We have that <math>b^2-a^2=2^{8n-4}+2^{4n-1}+1-2^{4n}=2^{8n-4}-2^{4n-1}+1=(2^{4n-2}-1)^2</math>
 +
We desire <math>A=a(b^2-a^2)=2^{2n}m^2</math>, or <math>2^{4n-2}-1=m</math>, and <math>m</math> is clearly always odd for positive <math>n</math>, completing the proof.
 +
 
 +
==Solution 4==
 +
 
 +
We simply need to provide an example for all <math>n</math> that satisfies the condition, and we do so.
 +
 
 +
Let <math>a = 2^{2n+1}+1</math>. Then consider the triangle with coordinates <math>(0,0), (a,a^2), (a^2,a^4) = (x_1, y_1), (x_2, y_2), (x_3, y_3)</math>.
 +
 
 +
 
 +
By the shoelace formula, this triangle has area <cmath>\frac{1}{2}|x_1y_2 - y_1x_2 + x_2y_3 - y_2x_3|=\frac{1}{2}|a(a^4)-a^2(a^2)|=\frac{1}{2}|a^5 - a^4| = \frac{a^4(a-1)}{2}=2^{2n}(2^{2n+1}+1)^4</cmath>which clearly can be written in the form <math>(2^n \times m)^2 = 2^{2n} \times m^2</math>, where <math>m^2 = (2^{2n+1}+1)^4</math> or <math>m=(2^{2n+1}+1)^2</math>. Now, we just have to prove that <math>(2^{2n+1}+1)^2</math> is always odd. This is true because <math>2^{2n+1}</math> is even (because it's a power of <math>2</math>), so <math>2^{2n+1}+1</math> is odd, and since an odd number squared is odd, the whole thing is odd as well. And we are done, since we have proved that for all <math>n</math>, we can show that there exists such a triangle by merely providing an example. <math>\square</math>
 +
 
 +
~thinker123
  
 
== See Also ==
 
== See Also ==

Latest revision as of 19:21, 11 September 2021

Problem

A triangle is called a parabolic triangle if its vertices lie on a parabola $y = x^2$. Prove that for every nonnegative integer $n$, there is an odd number $m$ and a parabolic triangle with vertices at three distinct points with integer coordinates with area $(2^nm)^2$.

A Small Hint

Before you read the solution, try using induction on n. (And don't step by one!)

Solution

Let the vertices of the triangle be $(a, a^2), (b, b^2), (c, c^2)$. The area of the triangle is the absolute value of $A$ in the equation:

\[A = \frac{1}{2}\det\left\vert \begin{array}{c c} b-a & c - a\\ b^2 - a^2 & c^2 - a^2 \end{array}\right\vert = \frac{(b-a)(c-a)(c-b)}{2}\]

If we choose $a < b < c$, $A > 0$ and gives the actual area. Furthermore, we clearly see that the area does not change when we subtract the same constant value from each of $a$, $b$ and $c$. Thus, all possible areas can be obtained with $a = 0$, in which case $A = \frac{1}{2}bc(c-b)$.

If a particular choice of $b$ and $c$ gives an area $A = (2^nm)^2$, with $n$ a positive integer and $m$ a positive odd integer, then setting $b' = 4b$, $c' = 4c$ gives an area $A' = 4^3 A = 8^2 A = (2^{n+3}m)^2$.

Therefore, if we can find solutions for $n = 0$, $n = 1$ and $n = 2$, all other solutions can be generated by repeated multiplication of $b$ and $c$ by a factor of $4$.

Setting $b=1$ and $c=2$, we get $A=1 = (2^0\cdot1)^2$, which yields the $n=0$ case.

Setting $b=1$ and $c=9$, we get $A = 9\cdot4 = (2^1\cdot3)^2$, which yields the $n=1$ case.

Setting $b=1$ and $c=5$, we get $A=1\cdot2\cdot5 = 10$. Multiplying these values of $b$ and $c$ by $10$, we get $b'=10$, $c'=50$, $A'=10\cdot20\cdot50 = 100^2 = (2^2\cdot5^2)^2$, which yields the $n=2$ case. This completes the construction.

Solution 2

We proceed via induction on n. Notice that we prove instead a stronger result: there exists a parabolic triangle with area $(2^nm)^2$ with two of the vertices sharing the same y-coordinate.

BASE CASE: If $n = 0$, consider the parabolic triangle $ABC$ with $A(0, 0), B(1, 1), C(-1, 1)$ that has area $1/2 \cdot 1 \cdot 2 = 1$, so that $n = 0$ and $m = 1$. If $n = 1$, let $ABC = A(5, 25), B(4, 16), C(-4, 16)$. Because $ABC$ has area $1/2 \cdot 8 \cdot 9 = 36$, we set $n = 1$ and $m = 3$. If $n = 2$, consider the triangle formed by $A(21, 441), B(3, 9), C(-3, 9)$. It is parabolic and has area $1/2 \cdot 6 \cdot 432 = 1296 = 36^2$, so $n = 2$ and $m = 9$.

INDUCTIVE STEP: If $n = k$ produces parabolic triangle $ABC$ with $A(a, a^2), B(b, b^2),$ and $C(-b, b^2)$, consider $A$'$B$'$C$' with vertices $A(4a, 16a^2)$, $B(4b, 16b^2)$, and $C(-4b, 16b^2)$. If $ABC$ has area $(2^km)^2$, then $A$'$B$'$C$' has area $(2^{k+3}m)^2$, which is easily verified using the $1/2 \cdot\text{base} \cdot \text{height}$ formula for triangle area. This completes the inductive step for $k \implies k+3$.

Hence, for every nonnegative integer $n$, there exists an odd $m$ and a parabolic triangle with area $(2^nm)^2$ with two vertices sharing the same ordinate. The problem statement is a direct result of this result. -MathGenius_

Solution 3 (without induction)

First, consider triangle with vertices $(0,0)$, $(1,1)$, $(-1,1)$. This has area $1$ so $n=0$ case is satisfied.

Then, consider triangle with vertices $(a,a^2), (-a,a^2), (b,b^2)$, and set $a=2^{2n}$ and $b=2^{4n-2}+1$. The area of this triangle is $\frac{1}{2} \cdot base \cdot height=a(b^2-a^2)$. We have that $b^2-a^2=2^{8n-4}+2^{4n-1}+1-2^{4n}=2^{8n-4}-2^{4n-1}+1=(2^{4n-2}-1)^2$ We desire $A=a(b^2-a^2)=2^{2n}m^2$, or $2^{4n-2}-1=m$, and $m$ is clearly always odd for positive $n$, completing the proof.

Solution 4

We simply need to provide an example for all $n$ that satisfies the condition, and we do so.

Let $a = 2^{2n+1}+1$. Then consider the triangle with coordinates $(0,0), (a,a^2), (a^2,a^4) = (x_1, y_1), (x_2, y_2), (x_3, y_3)$.


By the shoelace formula, this triangle has area \[\frac{1}{2}|x_1y_2 - y_1x_2 + x_2y_3 - y_2x_3|=\frac{1}{2}|a(a^4)-a^2(a^2)|=\frac{1}{2}|a^5 - a^4| = \frac{a^4(a-1)}{2}=2^{2n}(2^{2n+1}+1)^4\]which clearly can be written in the form $(2^n \times m)^2 = 2^{2n} \times m^2$, where $m^2 = (2^{2n+1}+1)^4$ or $m=(2^{2n+1}+1)^2$. Now, we just have to prove that $(2^{2n+1}+1)^2$ is always odd. This is true because $2^{2n+1}$ is even (because it's a power of $2$), so $2^{2n+1}+1$ is odd, and since an odd number squared is odd, the whole thing is odd as well. And we are done, since we have proved that for all $n$, we can show that there exists such a triangle by merely providing an example. $\square$

~thinker123

See Also

2010 USAJMO (Problems • Resources)
Preceded by
Problem 3 		Followed by
Problem 5
1 • 2 • 3 • 4 • 5 • 6
All USAJMO 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=2010_USAJMO_Problems/Problem_4&oldid=162073"