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

Posers and Puzzles

  1. 26 Apr '08 02:35
    Do there exist a set of 2008 positive integers such that the sum of any subset of these is never a perfect square? If so provide proof of existence or construction, and if not then also provide proof.
  2. 26 Apr '08 05:50
    Edit: I should mention that each of the numbers are distinct
  3. 26 Apr '08 12:00
    {2, 8, 32, 128, 512, 2^11, 2^13, 2^15, etc, 2^4017}

    I'm horrible at proofs, but I would suggest if you took that sequence out to 2008 terms, then you would have a set which met the conditions.

    My initial line of thinking in terms of proof is that if you prime factored the sum of any proper subset, you would find that you would have an odd number of 2's in the prime factorization. Since square number have an even number of every prime number they are divisible by in, the result is clearly not a square.

    You could sum none of them and get 0, but that's true of any subset, and not valid in my opinion.
  4. 26 Apr '08 12:52 / 2 edits
    Seems all right to me. But i am still not convinced that you will always get an odd number of 2's in the prime factorisation of the sum.

    EDIT: I'm convinced now. Proof:

    Take any subset, and consider the smallest element. Let this element be 2^2n+1. Then take each element of the subset mod (2^2n+2). Clearly, 2^2n+1 is congruent to 2^2n+1(mod 2^2n+2) and every other element is congruent to 0. The sum is therefore congruent to 2^2n+1(mod 2^2n+2) which is of course impossible for a perfect square. Well done geep.

    EDIT2: Spelling.
  5. 26 Apr '08 15:21 / 1 edit
    Originally posted by geepamoogle
    {2, 8, 32, 128, 512, 2^11, 2^13, 2^15, etc, 2^4017}

    I'm horrible at proofs, but I would suggest if you took that sequence out to 2008 terms, then you would have a set which met the conditions.

    My initial line of thinking in terms of proof is that if you prime factored the sum of any proper subset, you would find that you would have an odd number of could sum none of them and get 0, but that's true of any subset, and not valid in my opinion.
    Maybe it is easier to see if we use powers of 10:

    Let the set be {10, 10^3, 10^5, 10^7, ... , 10^4015}.

    The the sum of every non-empty subset ends with an odd number of 0's, so it cannot be a square.

    In your proof, write the numbers in base 2 and add the numbers in the chosen subset. Again, it is obvious that there are no carries in the addition so the sum ends with an odd number of 0's, but the square of every binary number ends with an even number of 0's.
  6. Standard member preachingforjesus
    Iron Pillar
    30 Apr '08 22:18
    Originally posted by David113
    Maybe it is easier to see if we use powers of 10:

    Let the set be {10, 10^3, 10^5, 10^7, ... , 10^4015}.

    The the sum of every non-empty subset ends with an odd number of 0's, so it cannot be a square.

    In your proof, write the numbers in base 2 and add the numbers in the chosen subset. Again, it is obvious that there are no carries in the addition so ...[text shortened]... an odd number of 0's, but the square of every binary number ends with an even number of 0's.
    Binary numbers: 111^10=110001

    this has an odd number of 0's
  7. Standard member forkedknight
    Defend the Universe
    30 Apr '08 22:25 / 1 edit
    he was talking about squares

    *edit* and that ^10 is in base 2, nevermind...
  8. Standard member forkedknight
    Defend the Universe
    30 Apr '08 22:37
    Originally posted by David113
    Maybe it is easier to see if we use powers of 10:

    Let the set be {10, 10^3, 10^5, 10^7, ... , 10^4015}.

    The the sum of every non-empty subset ends with an odd number of 0's, so it cannot be a square.

    In your proof, write the numbers in base 2 and add the numbers in the chosen subset. Again, it is obvious that there are no carries in the addition so ...[text shortened]... an odd number of 0's, but the square of every binary number ends with an even number of 0's.
    I'm not really sure what you're talking about saying that all squares in binary end in an odd number of 0's.

    Any power of 2 represented in binary has a square that ends in an EVEN number of 0's
  9. 01 May '08 12:59
    He is not saying that the binary representation has an odd number of zeroes, he is saying that the decimal representation has an odd number of zeros.