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 "2007 Indonesia MO Problems/Problem 8"

(Solution to Problem 8 (credit to crazyfehmy) -- perfect square shenans)
 
(→‎Solution (credit to crazyfehmy))
 
Line 3: Line 3:
 
Let <math> m</math> and <math> n</math> be two positive integers. If there are infinitely many integers <math> k</math> such that <math> k^2+2kn+m^2</math> is a perfect square, prove that <math> m=n</math>.
 
Let <math> m</math> and <math> n</math> be two positive integers. If there are infinitely many integers <math> k</math> such that <math> k^2+2kn+m^2</math> is a perfect square, prove that <math> m=n</math>.
  
−
==Solution (credit to crazyfehmy)==
+
==Solution 1 (credit to crazyfehmy)==
  
 
Note that we can [[Completing the square|complete the square]] to get <math>k^2 + 2kn + n^2 - n^2 + m^2</math>, which equals <math>(k+n)^2 + m^2 - n^2</math>.
 
Note that we can [[Completing the square|complete the square]] to get <math>k^2 + 2kn + n^2 - n^2 + m^2</math>, which equals <math>(k+n)^2 + m^2 - n^2</math>.
Line 33: Line 33:
 
<br>
 
<br>
 
Now we need to prove that if <math>m = n</math>, there are an infinite number of integers <math>k</math> that satisfy the original conditions.  By the Substitution Property, we find that <math>k^2 + 2kn + m^2 = k^2 + 2kn + n^2</math>.  The expression can be factored into <math>(k+n)^2</math>.  Since the expression is a perfect square, for all integer values of <math>n, k</math>, there are an infinite number of integers <math>k</math> that satisfies the original conditions when <math>m = n</math>.
 
Now we need to prove that if <math>m = n</math>, there are an infinite number of integers <math>k</math> that satisfy the original conditions.  By the Substitution Property, we find that <math>k^2 + 2kn + m^2 = k^2 + 2kn + n^2</math>.  The expression can be factored into <math>(k+n)^2</math>.  Since the expression is a perfect square, for all integer values of <math>n, k</math>, there are an infinite number of integers <math>k</math> that satisfies the original conditions when <math>m = n</math>.
 +
 +
==Solution 2 (credit to dskull16)==
 +
 +
We begin by completing the square to get <math>k^2 + 2kn + n^2 - n^2 + m^2</math>, which equals <math>(k+n)^2 + m^2 - n^2</math>.
 +
 +
<br>
 +
Then we have that <math>(k+n)^2 + m^2 - n^2 = a^2</math> for some natural number a.
 +
This then gives us <math>m^2 - n^2 = a^2 - (k+n)^2</math> which we can write like
 +
<math>(m+n)(m-n) = (a+k+n)(a-k-n)</math> by difference of two squares.
 +
 +
<br>
 +
Now we remark that the left hand side is a constant since we prematurely chose <math>m</math> and <math>n</math>. Acknowledging the fact that this equation is comprised entirely of integers, we see that <math>(a+k-n)</math> and <math>(a-k-n)</math> need both be factors of the left hand side of which there are finitely many. This means that there are finitely many solutions for <math>a</math>.
 +
 +
<br>
 +
If however the left hand side were 0, implying that either <math>m = n</math> or <math>m = -n</math>, we would be able to find infinitely many integers such that <math>a+k = n</math>. Since <math>m</math> and <math>n</math> are positive integers, this means that <math>m=n</math> as required.
  
 
==See Also==
 
==See Also==

Latest revision as of 18:08, 3 February 2024

Problem

Let $m$ and $n$ be two positive integers. If there are infinitely many integers $k$ such that $k^2+2kn+m^2$ is a perfect square, prove that $m=n$.

Solution 1 (credit to crazyfehmy)

Note that we can complete the square to get $k^2 + 2kn + n^2 - n^2 + m^2$, which equals $(k+n)^2 + m^2 - n^2$.


Assume that $m > n$. Since $m, n$ are positive, we know that $m^2 - n^2 > 0$. In order to prove that $(k+n)^2 + m^2 - n^2$ is not a perfect square, we can show that there are values of $k$ where $(k+n)^2 < (k+n)^2 + m^2 - n^2 < (k+n+1)^2$.


Since $m^2 - n^2 > 0$, we know that $(k+n)^2 < (k+n)^2 + m^2 - n^2$. In the case where $(k+n)^2 + m^2 - n^2 < (k+n+1)^2$, we can expand and simplify to get \begin{align*} k^2 + 2kn + n^2 + m^2 - n^2 &< k^2 + 2kn + n^2 + 2k + 2n + 1 \\ m^2 - n^2 &< 2k + 2n + 1 \\ \frac{m^2 - n^2 - 2n - 1}{2} &< k. \end{align*} All steps are reversible, so there are values of $k$ where $(k+n)^2 < (k+n)^2 + m^2 - n^2 < (k+n+1)^2$, so there are no values of $m, n$ where $m > n$ that results in infinite number of integers $k$ that satisfy the original conditions.


Now assume that $m < n$. Since $m, n$ are positive, we know that $m^2 - n^2 < 0$. In order to prove that $(k+n)^2 + m^2 - n^2$ is not a perfect square, we can show that there are values of $k$ where $(k+n-1)^2 < (k+n)^2 + m^2 - n^2 < (k+n)^2$.


Since $m^2 - n^2 < 0$, we know that $(k+n)^2 + m^2 - n^2 < (k+n)^2$. In the case where $(k+n-1)^2 < (k+n)^2 + m^2 - n^2$, we can expand and simplify to get \begin{align*} k^2 + 2kn + n^2 - 2k - 2n + 1 &< k^2 + 2kn + n^2 + m^2 - n^2 \\ -2k - 2n + 1 &< m^2 - n^2 \\ k &> -\frac{m^2 - n^2 + 2n - 1}{2}. \end{align*} All steps are reversible, so there are values of $k$ where $(k+n-1)^2 < (k+n)^2 + m^2 - n^2$, so there are no values of $m, n$ where $m < n$ that results in infinite number of integers $k$ that satisfy the original conditions.


Now we need to prove that if $m = n$, there are an infinite number of integers $k$ that satisfy the original conditions. By the Substitution Property, we find that $k^2 + 2kn + m^2 = k^2 + 2kn + n^2$. The expression can be factored into $(k+n)^2$. Since the expression is a perfect square, for all integer values of $n, k$, there are an infinite number of integers $k$ that satisfies the original conditions when $m = n$.

Solution 2 (credit to dskull16)

We begin by completing the square to get $k^2 + 2kn + n^2 - n^2 + m^2$, which equals $(k+n)^2 + m^2 - n^2$.


Then we have that $(k+n)^2 + m^2 - n^2 = a^2$ for some natural number a. This then gives us $m^2 - n^2 = a^2 - (k+n)^2$ which we can write like $(m+n)(m-n) = (a+k+n)(a-k-n)$ by difference of two squares.


Now we remark that the left hand side is a constant since we prematurely chose $m$ and $n$. Acknowledging the fact that this equation is comprised entirely of integers, we see that $(a+k-n)$ and $(a-k-n)$ need both be factors of the left hand side of which there are finitely many. This means that there are finitely many solutions for $a$.


If however the left hand side were 0, implying that either $m = n$ or $m = -n$, we would be able to find infinitely many integers such that $a+k = n$. Since $m$ and $n$ are positive integers, this means that $m=n$ as required.

See Also

2007 Indonesia MO (Problems)
Preceded by
Problem 7 		1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 Followed by
Last Problem
All Indonesia MO Problems and Solutions
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2007_Indonesia_MO_Problems/Problem_8&oldid=214391"