How to prove the following number theory puzzle

Question

Consider all the integers from 1-13. Without reusing any integers, find a set of three integers for which all numbers 1-13 may be created using only addition and subtraction. Prove that for all such sets, it is not possible to create a sum of 14.

For this question, I've identified that 1,3,9 is a possible set of integers that fulfill the requirements as follows:

$1 = 1 \\ 2 = 3 - 1 \\ 3 = 3 \\ 4 = 1 + 3 \\ 5 = 9 - 1 - 3 \\ 6 = 9 - 3 \\ 7 = 9 + 1 - 3 \\ 10 = 9 + 1 \\ 11 = 9 + 3 - 1 \\ 12 = 9 + 3 \\ 13 = 1 + 3 + 9$

The obvious reason that this set of integers will not add up to 14 is that their sum is 13, smaller than 14. Hence, we cannot get a sum of 14. But I'm not sure if this is the only set of integers that fulfill the requirements and therefore cannot prove that all of these sets of integers will not create a sum of 14. Is there a rule or property I may be overlooking?

Any assistance on this would be much appreciated!

Answer 1

Let $a,b,c$ the set of integers. The goal is to find $14$ ways to respectively get $1,2,\ldots,14$. Each of $a,b,c$ can be with sign $+$, $-$, or $0$ (latter meaning that it doesn't occur). This makes $3^3$ ways to get numbers this way.

Note that every combination has an opposite: for example $a+b-c$ is the opposite of $c-a-b$. At least one of then is $0$ or negative, so at least one of them is not valid, so we get at most $\lfloor27/2\rfloor=13$ different results. So it is impossible to get the integer numbers from $1$ to $14$.

Answer 2

Suppose your numbers are $\{a_1,a_2,a_3\}$. Then the set of combinations you consider is $$\left\{\sum \delta_ia_i\quad \text {where}\quad \delta_i\in \{0, \pm 1\}\right\}$$

A priori, there are $3^3=27$ such elements, but of course many of these are $≤0$. Indeed, you can always get $0$ (by taking $\delta_i=0$ for all $i$) and if $n$ is in the set, so is $-n$. Thus of the non-zero elements in the set, at most $\frac {27-1}2=13$ of them are positive. So if you can get all the thirteen numbers from $1-13$ you can't get anything else.