# 2008 numbers, #2

David113
Posers and Puzzles 26 Apr '08 15:24
1. 26 Apr '08 15:24
Is there a set of 2008 distinct positive integers, such that the sum of any 2007 of them is a perfect square?
2. forkedknight
Defend the Universe
26 Apr '08 23:254 edits
Originally posted by David113
Is there a set of 2008 distinct positive integers, such that the sum of any 2007 of them is a perfect square?
The set must sum to X^2 + Y, where Y is the smallest member of the set.

Other members of the set must be of the form X^2 + Y - (X-N)^2, where 1 lte N lte X

Once X gets sufficiently large, it becomes possible that there are 2008 squares whose sum differences are less than X^2 + 1, which is necessary, but that's about as far as I got.
3. 27 Apr '08 06:05
I tried considering the terms (mod 4), and got nowhere
4. 27 Apr '08 19:132 edits
Originally posted by David113
Is there a set of 2008 distinct positive integers, such that the sum of any 2007 of them is a perfect square?
Solving this is a fools errand. We have to set it up so that

(>"#" denotes subtext)

N>"1" + N>"2"... N>"2007"= (S>"1" ) ^2
N>"1" + N>"3"... N>"2007"= (S>"2" ) ^2
N>"1" + N>"4"... N>"2007"= (S>"3" ) ^2
N>"1" + N>"5"... N>"2007"= (S>"4" ) ^2
etc.

There would be

2008!/2007!

equations, or 2008 equations, with

2008+2007=4015

variables, which you would add so that

2007(N>"1"+N>"2"+...+N>"2007" )=(S>"1" )^2 + (S>"2" )^2 + ... + (S>"2008" )^2

So that

(S>"1" )^2 + (S>"2" )^2 + ... + (S>"2008" )^2

must be a multiple of 2007...

Then you use modular arithmetic. This is arithmetic that has in it things similar to a = b (mod x), which means that x is a divisor of a - b. Some examples would be if

100 = 79 (mod 7), because 100 - 79 = 21 has 7 as a divisor.

Also, if you divide, for example 20 by 7, the quotient is 14 and
remainder is 2, and 20 = 6 (mod 2).

So, it would be simple from here, if there were only 4 or 5 variables. With 2008, it will be very hard!

We need to find number values for which:

(S>"1" )^2 + (S>"2" )^2 + ... + (S>"2008" )^2 = 0 (mod 2007)

If you want to take it from there, you would have to do 2007 operations of logic in which you test congruency for integers for 1 mod 2007, 2 mod 2007, 3 mod 2007, etc. I don't feel like it.

As I said, this is a VERY hard problem, and I don't feel like finishing it! Ok?
5. 27 Apr '08 21:29
Originally posted by UzumakiAi
Solving this is a fools errand. We have to set it up so that

(>"#" denotes subtext)

N>"1" + N>"2"... N>"2007"= (S>"1" ) ^2
N>"1" + N>"3"... N>"2007"= (S>"2" ) ^2
N>"1" + N>"4"... N>"2007"= (S>"3" ) ^2
N>"1" + N>"5"... N>"2007"= (S>"4" ) ^2
etc.

There would be

2008!/2007!

equations, or 2008 equations, with

2008+2007=4015

variabl ...[text shortened]... I don't feel like finishing it! Ok?
Actually, there is a simple solution, without any hard work.
6. 27 Apr '08 21:50
Originally posted by David113
Actually, there is a simple solution, without any hard work.
Really?
7. 27 Apr '08 21:521 edit
Originally posted by David113
Actually, there is a simple solution, without any hard work.
Oh! Of course! It was yes/no question. Yes is the answer, it is always possible for a set of n numbers for there to be sums that are always perfect squares.

Is that right? (Of course it is!?)

I had thought you wanted the SPECIFIC numbers, not just whether it was possible.
8. 27 Apr '08 22:57
9. 27 Apr '08 23:09
Originally posted by Dejection
I provided way to find the answer in the previous post, if you do that you will find the numbers. There is no way that there aren't any. The equations would work out.
10. 28 Apr '08 13:14
Does modular arithmetic always produce answers? Seems to me that x^2+y^2=3 (mod 4) has no solution...
11. 29 Apr '08 00:55
Originally posted by Dejection
Does modular arithmetic always produce answers? Seems to me that x^2+y^2=3 (mod 4) has no solution...
You're right. But I'm lazy. I don't want to do proofs.
12. 29 Apr '08 12:44
Oh, by the way, just because it works in mod 2007, doesnt mean it actually works. E.g. X^2+Y^2=7 works mod 2, but clearly doesnt work in actuality. So using a mod argument is really only useful for proving non-existence. Proving existence is best done via a construction.
13. 03 May '08 13:025 edits
Here's what I've got,

Let us have a set S of 2008 distinct positive integers. Label them a1 through a2008.

In general, a set of n elements has exactly n subsets of n-1 elements (think of the combination number nCk where k = n-1). Let the sum of elements in each subset be denoted by s1 through s2008, i.e.

a1 + a2 + a3 + ... + a2007 = s1
a1 + a2 + a3 + ... + a2008 = s2
.
.
.
a2 + a3 + a3 + ... + a2008 = s2008

The system of these 2008 equations can be represented by a 2008x2008 matrix as so

1 1 1 ... 1 1 0
1 1 1 ... 1 0 1
.
.
.
0 1 1 ... 1 1 1

it is easy to check that the inverse of a such matrix with n rows
is

1/m 1/m 1/m ... 1/m 1/m (1/m)-1
1/m 1/m 1/m ... 1/m (1/m)-1 1/m
.
.
(1/m)-1 1/m 1/m ... 1/m 1/m 1/m

where m = n - 1

for example, for n = 6 the inverse matrix is

1/5 1/5 1/5 1/5 1/5 -4/5
1/5 1/5 1/5 1/5 -4/5 1/5
.
.
.
-4/5 1/5 1/5 1/5 1/5 1/5

Hence, the elements of our set S can be written in terms of the sums of subsets as

a1 = ( s1 + s2 + s3 + ... + s2006 + s2007 - 2006 * s2008 ) / 2007
a2 = ( s1 + s2 + s3 + ... + s2006 - 2006 * s2007 + s2008 ) / 2007
.
.
.
a2008 = ( -2006 * s1 + s2 + s3 + ... + s2006 + s2007 + s2008 ) / 2007

Since the elements of our set S are positive integers, the only two restrictions on the sums s1 through s2008 is that they must make the numerators positive and divisible by 2007.

Let M be a positive integer. Then take

s1 = ( M * 2007 )^2
s2 = ( (M+1) * 2007 )^2
.
.
.
s2008 = ( (M+2007) * 2007 )^2

Now clearly, all numerators are divisible by 2007. Furthermore, sice s1 < s2 < s3 < ... < s2006 < s2007 < s2008, a1 has the lowest numerator. Thus if a1's numerator is positive, so are all others.

Lets us look at ( s1 + s2 + s3 + ... + s2006 + s2007 - 2006 * s2008 ).

Using our equations for s1 through s2008, this is

( M * 2007 )^2 + ( (M+1) * 2007 )^2 + ( (M+2) * 2007 )^2 + ... + ( (M+2005) * 2007 )^2 + (M+2006) * 2007 )^2 - 2006 * (M+2007) * 2007 )^2

First we can factor out 2007^2 and we're left with M^2 + (M+1)^2 + (M+3)^2 + ... + (M+2005)^2 + (M+2006)^2 - 2006 * (M+2007)^2

If we collect the terms, we get plus M^2, 2007 times from s1 through s2007 and negative M^2 * 2006 from the last term, so we're left with 2007*M^2 - 2006*M^2 = M^2.

We could collect the other terms to obtain a quadratic equation and find the smallest value for M which will make numerator positive. But since the factor infront of M^2 in the quadratic is positive, we know that the quadratic itself must eventually be positive, i.e. there exists a positive interger M, such that a1 is positive.

then it's just the matter of computing s1 through s2008 and a1 through a2008.