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.

- Joined
- 12 Sep '07
- Moves
- 2668

- Joined
- 12 Sep '07
- Moves
- 2668

- 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.- Joined
- 12 Sep '07
- Moves
- 2668

26 Apr '08 12:522 editsSeems 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.- Joined
- 25 Aug '06
- Moves
- 0

26 Apr '08 15:211 edit

Maybe it is easier to see if we use powers of 10:*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.

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.- Joined
- 09 Nov '06
- Moves
- 14828

Backside of desert30 Apr '08 22:18

Binary numbers: 111^10=110001*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.

this has an odd number of 0's- Joined
- 18 Dec '03
- Moves
- 16172

127.0.0.1- Joined
- 18 Dec '03
- Moves
- 16172

127.0.0.130 Apr '08 22:37

I'm not really sure what you're talking about saying that all squares in binary end in an odd number of 0's.*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.

Any power of 2 represented in binary has a square that ends in an EVEN number of 0's- Joined
- 12 Sep '07
- Moves
- 2668