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 "1981 IMO Problems/Problem 3"

 
(template)
Line 1: Line 1:
 
== Problem ==
 
== Problem ==
  
−
Determine the maximum value of <math> \displaystyle m^2 + n^2 </math>, where <math> \displaystyle m </math> and <math> \displaystyle n </math> are integers satisfying <math> m, n \in \{ 1,2, \ldots , 1981 \} </math> and <math> \displaystyle ( n^2 - mn - m^2 )^2 = 1 </math>.
+
Determine the maximum value of <math>m^2 + n^2 </math>, where <math>m </math> and <math>n </math> are integers satisfying <math> m, n \in \{ 1,2, \ldots , 1981 \} </math> and <math>( n^2 - mn - m^2 )^2 = 1 </math>.
  
 
== Solution ==
 
== Solution ==
  
−
We first observe that since <math> \displaystyle \gcd(m,n)|1 </math>, <math>\displaystyle m</math> and <math>\displaystyle n</math> are [[relatively prime]].  In addition, we note that <math> \displaystyle n \ge m</math>, since if we had <math> \displaystyle n < m</math>, then <math> \displaystyle n^2 +nm -m^2 = n(n-m) - m^2 </math> would be the sum of two negative integers and therefore less than <math>\displaystyle -1</math>.  We now observe
+
We first observe that since <math>\gcd(m,n)|1 </math>, <math>m</math> and <math>n</math> are [[relatively prime]].  In addition, we note that <math>n \ge m</math>, since if we had <math>n < m</math>, then <math>n^2 +nm -m^2 = n(n-m) - m^2 </math> would be the sum of two negative integers and therefore less than <math>-1</math>.  We now observe
  
 
<center>
 
<center>
 
<math>
 
<math>
−
\displaystyle (m+k)^2 -(m+k)m - m^2 = -(m^2 - km - k^2)
+
(m+k)^2 -(m+k)m - m^2 = -(m^2 - km - k^2)
 
</math>,
 
</math>,
 
</center>
 
</center>
  
−
i.e., <math>\displaystyle (m,n) = (a,b) </math> is a solution [[iff]]. <math>\displaystyle (b, a+b) </math> is also a solution.  Therefore, for a solution <math>\displaystyle (m, n)</math>, we can perform the [[Euclidean algorithm]] to reduce it eventually to a solution <math> \displaystyle (1,n) </math>.  It is easy to verify that if <math>\displaystyle n </math> is a positive integer, it must be either 2 or 1.  Thus by trivial induction, all the positive integer solutions are of the form <math>\displaystyle (F_{n}, F_{n+1})</math>, where the <math>\displaystyle F_i</math> are the [[Fibonacci numbers]].  Simple calculation reveals 987 and 1597 to be the greatest Fibonacci numbers less than 1981, giving <math> \displaystyle 987^2 + 1597^2 </math> as the maximal value Q.E.D.
+
i.e., <math>(m,n) = (a,b) </math> is a solution [[iff]]. <math>(b, a+b) </math> is also a solution.  Therefore, for a solution <math>(m, n)</math>, we can perform the [[Euclidean algorithm]] to reduce it eventually to a solution <math>(1,n) </math>.  It is easy to verify that if <math>n </math> is a positive integer, it must be either 2 or 1.  Thus by trivial induction, all the positive integer solutions are of the form <math>(F_{n}, F_{n+1})</math>, where the <math>F_i</math> are the [[Fibonacci numbers]].  Simple calculation reveals 987 and 1597 to be the greatest Fibonacci numbers less than 1981, giving <math>987^2 + 1597^2 </math> as the maximal value Q.E.D.
  
  
 
{{alternate solutions}}
 
{{alternate solutions}}
  
−
== Resources ==
+
{{IMO box|num-b=1|num-a=3|year=1981}}
−
 
 
−
* [[1981 IMO Problems]]
 
−
* [http://www.artofproblemsolving.com/Forum/viewtopic.php?p=366642#p366642 Discussion on AoPS/MathLinks]
 
−
 
 
  
 
[[Category:Olympiad Number Theory Problems]]
 
[[Category:Olympiad Number Theory Problems]]

Revision as of 19:45, 25 October 2007

Problem

Determine the maximum value of $m^2 + n^2$, where $m$ and $n$ are integers satisfying $m, n \in \{ 1,2, \ldots , 1981 \}$ and $( n^2 - mn - m^2 )^2 = 1$.

Solution

We first observe that since $\gcd(m,n)|1$, $m$ and $n$ are relatively prime. In addition, we note that $n \ge m$, since if we had $n < m$, then $n^2 +nm -m^2 = n(n-m) - m^2$ would be the sum of two negative integers and therefore less than $-1$. We now observe

$(m+k)^2 -(m+k)m - m^2 = -(m^2 - km - k^2)$,

i.e., $(m,n) = (a,b)$ is a solution iff. $(b, a+b)$ is also a solution. Therefore, for a solution $(m, n)$, we can perform the Euclidean algorithm to reduce it eventually to a solution $(1,n)$. It is easy to verify that if $n$ is a positive integer, it must be either 2 or 1. Thus by trivial induction, all the positive integer solutions are of the form $(F_{n}, F_{n+1})$, where the $F_i$ are the Fibonacci numbers. Simple calculation reveals 987 and 1597 to be the greatest Fibonacci numbers less than 1981, giving $987^2 + 1597^2$ as the maximal value Q.E.D.


Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.

1981 IMO (Problems) • Resources
Preceded by
Problem 1 		1 • 2 • 3 • 4 • 5 • 6 Followed by
Problem 3
All IMO Problems and Solutions
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=1981_IMO_Problems/Problem_3&oldid=18774"