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.

  • 2
    $\begingroup$ You surely mean non-zero integers, otherwise we could use $20$ zeros. $\endgroup$ – Peter Nov 18 '16 at 14:17
  • $\begingroup$ 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? $\endgroup$ – Jens Nov 18 '16 at 20:23
  • $\begingroup$ Thanks @Jens I meant that sum of the elements in any subset should be a perfect square. I'll edit that. $\endgroup$ – Aditya P Nov 19 '16 at 6:56
  • $\begingroup$ @Peter I should have made that clear the trivial solution of $20$ zeros aren't allowed. Thanks $\endgroup$ – Aditya P Nov 19 '16 at 6:56
  • 1
    $\begingroup$ Can you get a set of size 3? $\endgroup$ – 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.)


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.