Please turn on javascript in your browser to play chess.
Posers and Puzzles

Posers and Puzzles

  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. Standard member forkedknight
    Defend the Universe
    26 Apr '08 23:25 / 4 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:13 / 2 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:52 / 1 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
    Generally, asking whether something exists implies asking for a proof, not a straight answer.
  9. 27 Apr '08 23:09
    Originally posted by Dejection
    Generally, asking whether something exists implies asking for a proof, not a straight answer.
    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:02 / 5 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.