wu :: forums - Print Page


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

        riddles >> easy >> Partitions of Square Numbers
        
(Message started by: THUDandBLUNDER on May 24^th, 2004, 10:24am)

Title: Partitions of Square Numbers
Post by THUDandBLUNDER on May 24^th, 2004, 10:24am

Find four distinct integers a,b,c,d such that:

1) 100 [smiley=leqslant.gif] a,b,c,d [smiley=leqslant.gif] 12000

2) The sum of all four of them is a perfect square.

3) The sum of any two of them is a perfect square.

Title: Re: Partitions of Square Numbers
Post by towr on May 24^th, 2004, 1:52pm

::[hide]3970, 386, 2114, 10430[/hide]::

Title: Re: Partitions of Square Numbers
Post by THUDandBLUNDER on May 24^th, 2004, 2:00pm

towr, your brevity explains why it's in Easy.

Any thoughts on a carbon-based approach?

Title: Re: Partitions of Square Numbers
Post by towr on May 24^th, 2004, 2:15pm

Yes, one, find a list with primitive pythagorean triangles (there's one floating around on the web with all with a hypothenuse smaller than 10000)

Silicon based methods might be troubled by a rather high complexity, depending on how brutishly one would like to force an answer out of it ;)

Title: Re: Partitions of Square Numbers
Post by Barukh on May 26^th, 2004, 10:19am

on 05/24/04 at 14:00:15, THUDandBLUNDER wrote:

Any thoughts on a carbon-based approach?

If a+b+c+d = Z², then it's almost obvious that Z is a hypotenuse of at least three Pythagorean triples (but not necessarily primitive). Taking the four given numbers in pairs, we also have:

a+b = A², c+d = B²;
a+c = C², b+d = D²;
a+d = E², b+c = F².
The general form of Z is given by (m² + n²)r, where m, n are co-prime, and r = 1 corresponds to primitive triples. The smallest possible Z is 65 = 5*13. It has two primitive (because 65 = 8² + 1² = 7² + 4²) and two non-primitive (from (3,4,5) and (5,12,13)) triples. It is more difficult to prove that 65 is the smallest, and it has to do with the fact that 65 is the smallest number factorized into two odd primes of the form 4x+1 (see Mathworld's page (http://mathworld.wolfram.com/PythagoreanTriple.html) for more info).

That gives the following 4 pairs corresponding to Z=65: (16, 63); (25, 60); (33, 56); (39, 52). To choose from these the six numbers A through F, we solve the above system and get:

a = (A²+C²-F²)/2,
b = (A²+F²-C²)/2,
c = (C²+F²-A²)/2,
d = B² – c = D² – b = E² – a,
which means that for d to be positive A, C, F must be the smaller number in the pair; and for a,b,c to be positive, their squares should obey the triangle's inequality. The only possibility is to choose A=25, C=33, F=39 (or any other permutation). This gives a = 193/2, b = 1057/2, c = 1985/2, d = 5215/2. This does not satisfy the conditions, but doubling Z and multiplying the numbers by 4 gives the solution (so quickly found by towr).

What happens if we take the next smallest Z? It's 85 = 17*5, it also generates 4 triples, and gives the solution with fractional numbers. Doubling it, we obtain (590, 4594, 5810, 17906) but the last number doesn't satisfy the second condition.

I hope I expressed myself more or less clearly… :)

But THUD&BLUNDER, why is it in Easy section (yes, I saw your explanation about towr's brevity).

Title: Re: Partitions of Square Numbers
Post by towr on May 26^th, 2004, 12:10pm

That's basicly the same thing I did..
The hardest part is probably finding the right pythagorean triples (those of the shape k*(3,4,5) are well known, but most people don't know any others, let alone how to contruct more). But if you allready have a list of them, I do think this is easy.