Posers and Puzzles

Posers and Puzzles

  1. Joined
    12 Sep '07
    Moves
    2668
    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. Joined
    12 Sep '07
    Moves
    2668
    26 Apr '08 05:50
    Edit: I should mention that each of the numbers are distinct
  3. Joined
    15 Feb '07
    Moves
    667
    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. Joined
    12 Sep '07
    Moves
    2668
    26 Apr '08 12:522 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. Joined
    25 Aug '06
    Moves
    0
    26 Apr '08 15:211 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. Backside of desert
    Joined
    09 Nov '06
    Moves
    14828
    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 memberforkedknight
    Defend the Universe
    127.0.0.1
    Joined
    18 Dec '03
    Moves
    16172
    30 Apr '08 22:251 edit
    he was talking about squares

    *edit* and that ^10 is in base 2, nevermind...
  8. Standard memberforkedknight
    Defend the Universe
    127.0.0.1
    Joined
    18 Dec '03
    Moves
    16172
    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. Joined
    12 Sep '07
    Moves
    2668
    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.
Back to Top