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"

(→‎Solution: clean up solution)
 
(One intermediate revision by one other user not shown)
Line 5: Line 5:
 
== Solution ==
 
== Solution ==
  
−
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
+
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
  
 
<cmath>
 
<cmath>

Latest revision as of 10:23, 13 May 2019

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=3524578$ as the maximal value.


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 2 		1 • 2 • 3 • 4 • 5 • 6 Followed by
Problem 4
All IMO Problems and Solutions
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=1981_IMO_Problems/Problem_3&oldid=105785"