Originally posted by David113The set must sum to X^2 + Y, where Y is the smallest member of the set.
Is there a set of 2008 distinct positive integers, such that the sum of any 2007 of them is a perfect square?
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.
- Joined
- 30 Dec 07
- Moves
- 9905
Originally posted by David113Solving this is a fools errand. We have to set it up so that
Is there a set of 2008 distinct positive integers, such that the sum of any 2007 of them is a perfect square?
(>"#" 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?
Originally posted by UzumakiAiActually, there is a simple solution, without any hard work.
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?
- Joined
- 30 Dec 07
- Moves
- 9905
Originally posted by David113Oh! 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.
Actually, there is a simple solution, without any hard work.
Is that right? (Of course it is!?)
I had thought you wanted the SPECIFIC numbers, not just whether it was possible.
- Joined
- 30 Dec 07
- Moves
- 9905
Originally posted by DejectionI 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.
Generally, asking whether something exists implies asking for a proof, not a straight answer.
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.
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.