Difference between revisions of "1981 IMO Problems/Problem 3"

Revision as of 19:46, 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 2	1 • 2 • 3 • 4 • 5 • 6	Followed by Problem 4
All IMO Problems and Solutions

@@ Line 18: / Line 18: @@
 {{alternate solutions}}
-{{IMO box|num-b=1|num-a=3|year=1981}}
+{{IMO box|num-b=2|num-a=4|year=1981}}
 [[Category:Olympiad Number Theory Problems]]

Page

Toolbox

Search

Difference between revisions of "1981 IMO Problems/Problem 3"

Revision as of 19:46, 25 October 2007

Problem

Solution