wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> putnam exam (pure math) >> Square Polynomial
        
(Message started by: THUDandBLUNDER on Jan 3rd, 2007, 9:44pm)
Title: Square Polynomial
Post by THUDandBLUNDER on Jan 3rd, 2007, 9:44pm
Find integers a,b,c such that  P(x) = ax2 + bx + c is not the square of a linear polynomial but P(n) is a perfect square for n = 1 to 4.
Title: Re: Square Polynomial
Post by Miles on Jan 4th, 2007, 6:58am
Could have [hide]a = -36, b = 180, c = -95, which gives P(1) = 49, P(2) = 121, P(3) = 121, P(4) = 49, and it is clear that P is not a square of a linear term as a is negative.[/hide]

I got this when I thought about plotting y = P(x) and realised that any quadratic going through the points
[hide] (1,m^2), (2,n^2), (3,n^2) and (4,m^2) where n > m >=0[/hide] would do the trick.  This gives a general result (but I'm not saying it covers all possible solutions) of
P(x) = [hide]-(1/2) * [(n^2-m^2)*x^2 - 5*(n^2-m^2)*x + 4n^2 - 6m^2][/hide]
Title: Re: Square Polynomial
Post by towr on Jan 4th, 2007, 7:20am
Here's a couple..

-8, 40, -32
-8, 40, -23
-6, 30, -20
-4, 20, -15
-2, 10, -8
2, -10, 12
6, -30, 40
8, -40, 48


[edit]
searching a bit further; the first one I found for which P(1) =/= P(4) and P(2) =/= P(3) :
a=-20, b=60, c=81 -> P([1,2,3,4]) = [121, 121, 81, 1]
[/edit]
Title: Re: Square Polynomial
Post by pex on Jan 4th, 2007, 7:21am
There are many more solutions. I found one (by programming, as usual; never mind that this is the Putnam thread) that gives distinct squares for n = 1 to 7:

[hide]P(x) = -4980x2 + 37620x - 16511[/hide]
Title: Re: Square Polynomial
Post by Miles on Jan 4th, 2007, 8:10am
Nice, but I do mind that this is the "Putnam" thread.  Can anyone provide an algebraic method to derive these polynomials?

Is there a limit to k such that there exists P with P(1), P(2), ... P(k) all square?
Title: Re: Square Polynomial
Post by Barukh on Jan 4th, 2007, 9:42am
Let me present here one approach that may be considered “algebraic”.

Relax one condition of the problem (say x = 1). Then, three coefficients a, b, c are determined uniquely by three chosen numbers P(2) = p2, P(3) = q2, P(4) = r2, by solving a system of linear equations with 3 unknowns. The general solution, of course, will express the coefficients a, b, c in terms of p2, q2, r2 (I don’t present them here, but they are pretty easy to derive, even online).

Now bringing back the forth condition, P(1) = a + b + c = s2. Using the above mentioned expressions, we get the following equality:

3(p2 - q2) + r2 = s2

The easiest way is to set p = q, and then r = s. Letting p = 3, r = 1, we get (a,b,c) = (-4, 20, -15).

But we want something more interesting! One way to proceed is to choose p2 - q2 to be an odd number, and then find r, s by factoring the left-hand side. The problem with this is that you too often end up with the square of the linear polynomial! Nevertheless, without using any computing power, I’ve found the following triple: (p, q, r) = (4, 1, 22), which produces the polynomial (249, -1260, 1540) with  4 disitinct squares 529, 16, 1, 484.

Unfortunately, this method doesn’t generalize to greater number of points.
h
Title: Re: Square Polynomial
Post by THUDandBLUNDER on Jan 4th, 2007, 10:18am

on 01/04/07 at 08:10:16, Miles wrote:
Nice, but I do mind that this is the "Putnam" thread.  Can anyone provide an algebraic method to derive these polynomials?

Is there a limit to k such that there exists P with P(1), P(2), ... P(k) all square?

I also sorta mind.

Let P(x) = d(2x - 5)2 + e
Then
P(1) = P(4) = 9d + e = p2
P(2) = P(3) =   d + e = q2
Hence
8d = p2 - q2
8e = 9q2 - p2
eg, putting p = 1, q = 3 gives d = -1, e = 10
and P(x) = -4x2 + 20x - 15
Title: Re: Square Polynomial
Post by THUDandBLUNDER on Jan 4th, 2007, 10:39am
For 8 squares we can try 2x-9 instead of 2x-5
We then get
P(1) = P(8) = 49d + e = r2
P(2) = P(7) = 25d + e = s2
P(3) = P(6) =   9d + e = p2
P(4) = P(5) =     d + e = q2
Giving
24d = 3p2 - 3q2 = r2 - s2
24e = 27q2 - 3p2 = 49s2 - 25r2

And only now should we unleash Pavlov's dogs, the CS nerds.    ;)

Ha! Too slow.
d = -105
e = 5434
p = 67
q = 73
r = 17
s = 53
and
P(x) = -420x2 + 3780x - 3071
Title: Re: Square Polynomial
Post by towr on Jan 4th, 2007, 11:20am
If we set the first two squares to hit at 0 and 1, we get the system

a + b + c = 0
4a + 2b + c = 1
9a + 3b + c = n2
16a + 4b + c = m2

from which we can derive
a = (n2 - 2)/2
b = (8 - 3n2)/2
c = n2 - 3
n2 = (m2 + 3)/3

from which we can see
n is even
and because we dont' want a square of a linear polynomial (and thus 4ac =/=b2)
n2 (n2 - 8) =/= -16 -> n=/= +-2

Now for
n2 = (m2 + 3)/3
We can find a recurrence
N1 = 1
N2=2
Nk = 4Nk-1 - Nk-2

And so we get solutions for
n m
26 45
362 627
5042 5733
70226 121635
etc

The first gives
a=337
b=-1010
c=673


NB, the first with 8 squares:
a=-420, b=3780, c=-3071
(for a,b,c under 5000 there's no longer sequence)
Title: Re: Square Polynomial
Post by towr on Jan 4th, 2007, 11:26am

on 01/04/07 at 10:39:23, THUDandBLUNDER wrote:
Ha! Too slow.
I already had it several hours ago.
But you seemed mindfull against such results..
Title: Re: Square Polynomial
Post by THUDandBLUNDER on Jan 4th, 2007, 11:33am

on 01/04/07 at 11:26:29, towr wrote:
I already had it several hours ago.
But you seemed mindfull against such results..

The margin doesn't count.   :P
OK, I believe you.
Title: Re: Square Polynomial
Post by THUDandBLUNDER on Jan 5th, 2007, 9:08am
And
d = 570570
e = 4406791
p = 3089
q = 2231
r = 5689
s = 4321
gives
2282280x2 - 20540520x + 50622961    
P(1) = P(8) = 56892
P(2) = P(7) = 43212
P(3) = P(6) = 30892
P(4) = P(5) = 22312


Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board