# Sum of any subset of 20 integers should be a perfect square

I am unsure about the exact details of the question. But it asks us to find a set of $20$ non-zero integers such that the sum of all the elements in any of its subsets should yield a perfect square.

I don't think this is possible and am unable to make headway. If any modified form of this question is solvable please mention that.

If it's not possible to construct such a set we should prove why it's not possible to find such a set.

• You surely mean non-zero integers, otherwise we could use $20$ zeros. – Peter Nov 18 '16 at 14:17
• I'm confused. Do you mean, as your title says, the sum of any subset or do you mean the sum of all subsets, as you write in the post? – Jens Nov 18 '16 at 20:23
• Thanks @Jens I meant that sum of the elements in any subset should be a perfect square. I'll edit that. – Aditya P Nov 19 '16 at 6:56
• @Peter I should have made that clear the trivial solution of $20$ zeros aren't allowed. Thanks – Aditya P Nov 19 '16 at 6:56
• Can you get a set of size 3? – djechlin Nov 19 '16 at 7:07

It's impossible as stated. Here's a sketch of a not-so-elegant disproof:

Call the numbers $A = \{a_i\}$ By considering subsets of size one, this implies each element ${a_i}$ has to be positive, and itself has to be a square.

Also, each of the $\{a_i\}$ must be distinct; if any two of them were the same (say $a_j = X^2$), then we could pick a size-two subset whose sum $a_j + a_k = 2X^2$ could not be a square.

Now consider congruences modulo 4. Note that modulo 4, perfect squares $\equiv$ 0 or 1. 2 or 3 are impossible. Hence each of the ${a_i} \equiv 0,1 (mod 4)$.

Next by considering subsets of size two, if at least two of the ${a_i} \equiv 1 (mod 4)$, then we'd be able to construct some size-two subset which was $\equiv 2$, hence couldn't be a square. Hence at least 19 of the 20 ${a_i} \equiv 0 (mod 4)$, and the other one $\equiv 0,1$.

So we've heavily constrained $A$. In fact we can use similar arguments for B = 6, 12, 60, 420 etc. to conclude 19 of the ${a_i} \equiv 0 (mod B)$. We can keep picking bases B, without limit (just keep multiplying by next unused prime), to prove that the gaps between the ${a_i}$ are infinite, hence A cannot exist. (Remember, the $\{a_i\}$ must be distinct).

Then, at least for this statement of it, the best you can do is A = {one positive square and nineteen zeros}.

(If the question was to have solutions, it must have been restricted somehow, e.g. "sum of all the elements in any of its size-n subsets should yield a perfect square". For some n.)