Home Profile Projects Articles

Answer: Another Putnam Problem (Dec 2, 2007)

Saturday, 8 of December , 2007 at 12:57 pm

Apparently, I bit off more than I could chew when tackling this question. I don’t have formal mathematical solution to this problem, but I will show you what I came up with.

Question: Determine the maximum value of m^2 + n^2, where m and n are integers in the range 1,2,…,1981 satisfying (n^2 - mn - m^2)^2 = 1.

Analysis: In an attempt to maximize m^2 + n^2, we should first investigate what values of m and n satisfy the constraints (n^2 - mn - m^2)^2 = 1 which can be reduced to n^2 - mn - m^2 = \pm 1. If we look for solutions to this equation for small values of m and n, you will find the following sequence:

(m,n) = (1,1), (1,2), (2,3)\ldots

The solution appears to be Fibonacci numbers. This would mean that if (m, n) are solutions then (n, m+n) would also be a solution. If we put (n, m+n) into the constraints, we can verify that all Fibonacci numbers are a solution.

(m+n)^2 - n(m+n) - n^2
m^2 + 2mn + n^2 - nm - n^2 -n^2
m^2 + nm - n^2 = - (n^2 -mn -m^2) = \pm 1

This shows that the following sequence is a solution to the given constraints:

(1,1), (1,2), (2,3), (3,5), (5,8), (8,13), (13,21), (21,34),
(34,55), (55,89), (89,144), (144,233),(233,377),(377,610),
(610,987),(987,1597),(1597,2584)\ldots (n-m,m),(m,n),(n,m+n)

The part that I wasn’t able to prove is that the Fibonacci numbers are the ONLY solution to the constraints. However, if they were, the function m^2 + n^2 would be maximized when (m,n) = (987,1597).

In order to prove that this was the correct solution, I wrote the following perl script:

$max_val = 0;
$max_m = 0;
$max_n = 0;
 
for ($m = 1; $m < 1982; $m++) {
   for ($n = 1; $n < 1982; $n++) {
      $val = $n*$n - $m*$n - $m*$m;
      $val = $val*$val;
 
      if($val == 1){
         $val = $m*$m + $n*$n;
 
         if($val > $max_val){
            $max_val = $val;
            $max_m = $m;
            $max_n = $n;
         }
      }
   }
}
 
print "Max Value: ".$max_val." m: ". $max_m." n: ".$max_n;

This script confirmed that the maximum value is when (m,n) = (987,1597)

$ perl find.pl
Max Value: 3524578 m: 987 n: 1597

Leave a comment

Category: Answers, Putnam Problems

Question: Another Putnam Problem (Dec 2, 2007)

Sunday, 2 of December , 2007 at 7:59 pm

This week has been really busy, so I haven’t put a lot of thought into my weekly question. I was reading about problems dealing with rotating frames of references and gravitational fields in my Classical Mechanics Textbook, but I couldn’t find any interesting problems. I decided to follow Rod from Reasonable Deviations and post today’s Putnam problem from the Harvard Mathematics Website.

Question: Determine the maximum value of m^2 + n^2, where m and n are integers in the range 1,2,…,1981 satisfying (n^2 - mn - m^2)^2 = 1

Leave a comment

Category: Putnam Problems, Questions

Analysis of Today’s Putman Problem

Wednesday, 28 of November , 2007 at 12:18 am

I found an interesting problem on the blog Reasonable Deviations.

Question:
Given a plane k, a point P in the plane and a point Q not in the plane, find all points R in k such that the ratio \frac{QP+PR}{QR} is a maximum.

Solution:
First, create a plane that intersects the points Q, P, and R. In addition to these 3-points, I’m going to create a 4th point point called R’ which is perpendicular to the plane.


Using Pythagoras Theorem, we can do the following:
\frac{QP+PR}{QR} = \frac{\sqrt{QR^{\prime 2}+PR^{\prime 2}}+RR^{\prime}+PR^{\prime}}{\sqrt{QR^{\prime 2}+RR^{\prime 2}}}

We can simplify the formula by using the following relations: x = RR^{\prime}, y = QR^{\prime}, z = PR^{\prime}. The important thing to note is that x is the only variable. The other variables are constant.

The formula can be reduced to:

f(x) = \frac{\sqrt{y^{2}+z^{2}}+x+z}{\sqrt{y^{2}+x^{2}}}

The maximum of f(x) will occur when its derivative is 0. Therefore,

\frac{d}{dx}f(x) = \frac{d}{dx}(\frac{\sqrt{y^{2}+z^{2}}+x+z}{\sqrt{y^{2}+x^{2}}}) = 0

\frac{d}{dx}f(x) = \frac{1}{\sqrt{y^{2}+x^{2}}}-\frac{(\sqrt{y^{2}+z^{2}}+x+z)x}{(y^{2}+x^{2})^{\frac{3}{2}}} = 0

\frac{1}{\sqrt{y^{2}+x^{2}}} = \frac{(\sqrt{y^{2}+z^{2}}+x+z)x}{(y^{2}+x^{2})^{\frac{3}{2}}}

y^{2}+x^{2} = (\sqrt{y^{2}+z^{2}}+x+z)x

y^{2} = (\sqrt{y^{2}+z^{2}}+z)

x = \frac{y^{2}}{\sqrt{y^{2}+z^{2}}+z}

Therefore, the point R will a distance x away from R’ defined by the following equation:

RR^{\prime} = \frac{QR^{\prime 2}}{QP+PR^{\prime}}

RR^{\prime} = \frac{QP^2-PR^{\prime 2}}{QP+PR^{\prime}}

RR^{\prime} = \frac{(QP-PR^{\prime})(QP+PR^{\prime})}{QP+PR^{\prime}}

RR^{\prime} = QP-PR^{\prime}

PR=QP

Comments (6)

Category: Answers, Putnam Problems, Questions