13
$\begingroup$

There are numbers $1, 2,3,4,5,6,7$ and signs '$+$' and '$-$'. Using only these numbers and signs, you can compose expressions and calculate the sum (difference). Concatenation operation is not valid.

Edit. Each number must be used exactly once and each sign can be used any number of times (from 0 to 7).

The minimum number is $-1-2-3-4-5-6-7 = -28$ and the maximum number is $1 + 2 + 3 + 4 + 5 + 6 + 7 = 28$, and these can only be obtained in a single way.

Question:

1) Is it possible to compose the remaining integers from the range $(-28, 28)$?

2) If an integer from the range $(-28, 28)$ can be composed, how many ways exist?

$\endgroup$
4
  • 1
    $\begingroup$ Must all numbers be used, or can a subset be used? (e.g. would $7=7$ count?) $\endgroup$
    – Anon
    Commented May 17, 2020 at 2:38
  • $\begingroup$ One must use all numbers. $\endgroup$
    – Nick
    Commented May 17, 2020 at 3:06
  • 2
    $\begingroup$ The restriction is that each number must be used exactly once and each sign can be used any number of times? It's not explicitly very clear but this seems to be the only way to make this a non-trivial puzzle. $\endgroup$
    – Alex Jones
    Commented May 18, 2020 at 1:08
  • 1
    $\begingroup$ @alexanderj93, i have edited the content. $\endgroup$
    – Nick
    Commented May 18, 2020 at 1:28

6 Answers 6

13
$\begingroup$

Let's answer the question 2:

We can write a generating function for the number of combinations. The number $1$ is present either with a $+$ or a $-$, which gives 1 way of making $1$ and 1 way of making $-1$. We will encode these data with a polynomial $z + z^{-1}$. Similarly, we writer $z^2 + z^{-2}$ for the number 2, etc. up to $z^7 + z^{-7}$. The product of all of those polynomials, $G = \prod_{n=1}^7 (z^n + z^{-n})$, is also a polynomial, and the coefficient at any $z^{k}$ is exactly the number of ways to obtain the sum of $k$. (If the term with $z^k$ is not present at all, the coefficient is zero and the sum of $k$ cannot be achieved at all.)

We can immediately answer the question 1 if we notice that

$G = \prod_{n=1}^7 (z^n + z^{-n})$ can be written as $G = z^{-28} \prod_{n=1}^7 (z^{2n}+1)$. This contains all even powers between $z^{-28}$ and $z^{28}$ (the coefficients are always only a sum of some +1's, i. e. nonzero); so all even numbers can be achieved and no odd number can be achieved.

If there were more than 7 numbers, then it would make sense to try to come up with some algebraic tricks, but

here we can just put it into Sage to get $$G = z^{28} + z^{26} + z^{24} + 2 \, z^{22} + 2 \, z^{20} + 3 \, z^{18} + 4 \, z^{16} + 5 \, z^{14} + 5 \, z^{12} + 6 \, z^{10} + 7 \, z^{8} + 7 \, z^{6} + 8 \, z^{4} + 8 \, z^{2} + 8 + \frac{8}{z^{2}} + \frac{8}{z^{4}} + \frac{7}{z^{6}} + \frac{7}{z^{8}} + \frac{6}{z^{10}} + \frac{5}{z^{12}} + \frac{5}{z^{14}} + \frac{4}{z^{16}} + \frac{3}{z^{18}} + \frac{2}{z^{20}} + \frac{2}{z^{22}} + \frac{1}{z^{24}} + \frac{1}{z^{26}} + \frac{1}{z^{28}}.$$ Other people have already explained why there can be only even sums. This shows that, out of those, the sums ±28 to ±24 have a single combination of signs, ±22 and ±20 two, ±18 three, ±16 four, ±14 and ±12 five, ±10 six, ±8 and ±6 seven and ±4, ±2 and 0 eight.

$\endgroup$
4
  • $\begingroup$ What the Sage means in your answer? $\endgroup$
    – Nick
    Commented May 17, 2020 at 9:47
  • 1
    $\begingroup$ @Nick, Sage (or better SageMath) is a free/libre open-source computer algebra system. I used that program to expand the product for me. The homepage is sagemath.org , if you want to know more. $\endgroup$
    – Ramillies
    Commented May 17, 2020 at 9:52
  • 1
    $\begingroup$ I feel disappointed this answer isn't getting more recognition as it's the only current answer that answers the entire problem (it answers question 2 and implicitly 1 as well) and does so in a simple and elegant way. $\endgroup$
    – Anon
    Commented May 18, 2020 at 1:30
  • $\begingroup$ @ramillies, please add to your text a short answer on the 1st question, then I can tick up. $\endgroup$
    – Nick
    Commented May 19, 2020 at 23:28
11
$\begingroup$

Question $1$:

It is impossible to construct all integers from $-28$ to $28$.

Proof:

We can first let all numbers to have positive values. So we have $$+ 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 = 28$$ If we want to create another equation, we will flip the pluses into minuses. Observe that, if we flip the plus before $x$, then the result will be decreased by $2x$! (For example, flipping $+5$ to $-5$ will create a result of $18$.)

So what can we say from this?

As each flipping will decrease the result by an even number, therefore the odd integer will never appear as a final result!

Question $2$:

This may not be a "simple" task. Anyway, this can be solved by a Dynamic Programming approach, but the table will be $28 \times 8$ long. I will not cover this part, but we can have a theory about how to calculate them.

So how many ways to get a final result i.e. $N$?

You could see from the proof on Question $1$, we can start with all numbers as pluses. This is the only way to get $N=28$. Let me give you an example of how to calculate for $N=10$ as a proof sketch. As flipping the plus before $x$ will decrease the final result by $2x$, note that for $N=10$ we want to decrease the final result by $28-10=18$. Therefore, we have to flip the plus before some numbers such that the sum of those numbers are $\frac{18}{2}=9$! There are several ways e.g. flipping $\{2,7\}$ or $\{4,5\}$ or even $\{2,3,4\}$.

So what's the exact formula?

If $N$ is odd then the answer is $0$. If $N$ is even, calculate $Y = \frac{28-N}{2}$. The answer is the number of sets consisting integers from $1$ to $7$ such that the sum of these numbers are $Y$.

$\endgroup$
19
  • 1
    $\begingroup$ Why is the number of sets consisting integers from 1 to 8? May be from 1 to 7 only? $\endgroup$
    – Nick
    Commented May 17, 2020 at 3:13
  • $\begingroup$ @Nick whoops, sorry that was purely a typo, will fix this. $\endgroup$
    – athin
    Commented May 17, 2020 at 3:33
  • 1
    $\begingroup$ You still have an 8, in your 2nd hidden box. $\endgroup$ Commented May 17, 2020 at 13:47
  • 1
    $\begingroup$ @tgm1024--Monicawasmistreated yes that's correct for generalizing the numbers of $1-7$ to any numbers. Anyway ah yes I have that on my second hidden box, but that's ok I guess.. If I code a program, I might extend that to $8$ just for the final check (if the equation results in $N$) :) $\endgroup$
    – athin
    Commented May 17, 2020 at 14:20
  • 2
    $\begingroup$ The total number of possibilities is 2^7 = 128, not 28*8 = 224. Either way, that's a laughably small number for a computer, so dynamic programming is not required. Also your final equation is wrong - it gives a sum of 105 ways to make the non-negative integers, and 301(!?) to make the negative ones. $\endgroup$ Commented May 18, 2020 at 2:23
6
$\begingroup$

Partial answer a)

Only even number can be composed.

Reason:

Changing $+n$ to $-n$ will have a decrease of $2n$, and vice versa, we will have an increase of $2n$. So the parity of the equation will not be changed, which means we can only get even results.

$\endgroup$
4
$\begingroup$

For those interested in a full list of ways, here it is:

-28 (1 ways) = -1-2-3-4-5-6-7 -26 (1 ways) = 1-2-3-4-5-6-7 -24 (1 ways) = -1+2-3-4-5-6-7 -22 (2 ways) = -1-2+3-4-5-6-7 = 1+2-3-4-5-6-7 -20 (2 ways) = -1-2-3+4-5-6-7 = 1-2+3-4-5-6-7 -18 (3 ways) = -1-2-3-4+5-6-7 = 1-2-3+4-5-6-7 = -1+2+3-4-5-6-7 -16 (4 ways) = -1-2-3-4-5+6-7 = 1-2-3-4+5-6-7 = -1+2-3+4-5-6-7 = 1+2+3-4-5-6-7 -14 (5 ways) = -1-2-3-4-5-6+7 = 1-2-3-4-5+6-7 = -1+2-3-4+5-6-7 = -1-2+3+4-5-6-7 = 1+2-3+4-5-6-7 -12 (5 ways) = 1-2-3-4-5-6+7 = -1+2-3-4-5+6-7 = -1-2+3-4+5-6-7 = 1+2-3-4+5-6-7 = 1-2+3+4-5-6-7 -10 (6 ways) = -1+2-3-4-5-6+7 = -1-2+3-4-5+6-7 = 1+2-3-4-5+6-7 = -1-2-3+4+5-6-7 = 1-2+3-4+5-6-7 = -1+2+3+4-5-6-7 -8 (7 ways) = -1-2+3-4-5-6+7 = 1+2-3-4-5-6+7 = -1-2-3+4-5+6-7 = 1-2+3-4-5+6-7 = 1-2-3+4+5-6-7 = -1+2+3-4+5-6-7 = 1+2+3+4-5-6-7 -6 (7 ways) = -1-2-3+4-5-6+7 = 1-2+3-4-5-6+7 = -1-2-3-4+5+6-7 = 1-2-3+4-5+6-7 = -1+2+3-4-5+6-7 = -1+2-3+4+5-6-7 = 1+2+3-4+5-6-7 -4 (8 ways) = -1-2-3-4+5-6+7 = 1-2-3+4-5-6+7 = -1+2+3-4-5-6+7 = 1-2-3-4+5+6-7 = -1+2-3+4-5+6-7 = 1+2+3-4-5+6-7 = -1-2+3+4+5-6-7 = 1+2-3+4+5-6-7 -2 (8 ways) = -1-2-3-4-5+6+7 = 1-2-3-4+5-6+7 = -1+2-3+4-5-6+7 = 1+2+3-4-5-6+7 = -1+2-3-4+5+6-7 = -1-2+3+4-5+6-7 = 1+2-3+4-5+6-7 = 1-2+3+4+5-6-7 0 (8 ways) = 1-2-3-4-5+6+7 = -1+2-3-4+5-6+7 = -1-2+3+4-5-6+7 = 1+2-3+4-5-6+7 = -1-2+3-4+5+6-7 = 1+2-3-4+5+6-7 = 1-2+3+4-5+6-7 = -1+2+3+4+5-6-7 2 (8 ways) = -1+2-3-4-5+6+7 = -1-2+3-4+5-6+7 = 1+2-3-4+5-6+7 = 1-2+3+4-5-6+7 = -1-2-3+4+5+6-7 = 1-2+3-4+5+6-7 = -1+2+3+4-5+6-7 = 1+2+3+4+5-6-7 4 (8 ways) = -1-2+3-4-5+6+7 = 1+2-3-4-5+6+7 = -1-2-3+4+5-6+7 = 1-2+3-4+5-6+7 = -1+2+3+4-5-6+7 = 1-2-3+4+5+6-7 = -1+2+3-4+5+6-7 = 1+2+3+4-5+6-7 6 (7 ways) = -1-2-3+4-5+6+7 = 1-2+3-4-5+6+7 = 1-2-3+4+5-6+7 = -1+2+3-4+5-6+7 = 1+2+3+4-5-6+7 = -1+2-3+4+5+6-7 = 1+2+3-4+5+6-7 8 (7 ways) = -1-2-3-4+5+6+7 = 1-2-3+4-5+6+7 = -1+2+3-4-5+6+7 = -1+2-3+4+5-6+7 = 1+2+3-4+5-6+7 = -1-2+3+4+5+6-7 = 1+2-3+4+5+6-7 10 (6 ways) = 1-2-3-4+5+6+7 = -1+2-3+4-5+6+7 = 1+2+3-4-5+6+7 = -1-2+3+4+5-6+7 = 1+2-3+4+5-6+7 = 1-2+3+4+5+6-7 12 (5 ways) = -1+2-3-4+5+6+7 = -1-2+3+4-5+6+7 = 1+2-3+4-5+6+7 = 1-2+3+4+5-6+7 = -1+2+3+4+5+6-7 14 (5 ways) = -1-2+3-4+5+6+7 = 1+2-3-4+5+6+7 = 1-2+3+4-5+6+7 = -1+2+3+4+5-6+7 = 1+2+3+4+5+6-7 16 (4 ways) = -1-2-3+4+5+6+7 = 1-2+3-4+5+6+7 = -1+2+3+4-5+6+7 = 1+2+3+4+5-6+7 18 (3 ways) = 1-2-3+4+5+6+7 = -1+2+3-4+5+6+7 = 1+2+3+4-5+6+7 20 (2 ways) = -1+2-3+4+5+6+7 = 1+2+3-4+5+6+7 22 (2 ways) = -1-2+3+4+5+6+7 = 1+2-3+4+5+6+7 24 (1 ways) = 1-2+3+4+5+6+7 26 (1 ways) = -1+2+3+4+5+6+7 28 (1 ways) = 1+2+3+4+5+6+7

The above was generated using this Java code:

Map<Integer, List<Integer>> resultFreq = new TreeMap<>();
for (int signMask = 0; signMask < (1 << 7); signMask++) {
    int result = 0;
    for (int i = 0; i < 7; i++) {
        if ((signMask & (1 << i)) == 0)
            result += i + 1;
        else
            result -= i + 1;
    }
    resultFreq.computeIfAbsent(result, k -> new ArrayList<>()).add(signMask);
}

StringBuilder buf = new StringBuilder();
for (Entry<Integer, List<Integer>> entry : resultFreq.entrySet()) {
    buf.setLength(0);
    buf.append(String.format("%3d (%d ways)", entry.getKey(), entry.getValue().size()));
    for (int signMask : entry.getValue()) {
        buf.append(" = ");
        for (int i = 0; i < 7; i++)
            buf.append((signMask & (1 << i)) != 0 ? '-' : i > 0 ? '+' : ' ').append(i + 1);
    }
    System.out.println(buf);
}
$\endgroup$
0
3
$\begingroup$

Because everyone made mathematical proof. I've decided I'm going to try adding a little value on the puzzle and give a solution for each possible case even if it is not part of the puzzle. I also like seeing it 'solved', not only formulas :)

$$-28 = -1-2-3-4-5-6-7$$ $$-26 = 1-2-3-4-5-6-7$$ $$-24 = -1+2-3-4-5-6-7$$ $$-22 = -1-2+3-4-5-6-7$$ $$-20 = -1-2-3+4-5-6-7$$ $$-18 = -1-2-3-4+5-6-7$$ $$-16 = -1-2-3-4-5+6-7$$ $$-14 = -1-2-3-4-5-6+7$$ $$-12 = 1-2-3-4-5-6+7$$ $$-10 = -1+2+3+4-5-6-7$$ $$-8 = -1-2-3+4-5+6-7$$ $$-6 = -1-2-3-4+5+6-7$$ $$-4 = 1-2-3-4+5+6-7$$ $$-2 = -1-2-3-4-5+6+7$$ $$0 = 1-2-3-4-5+6+7$$ $$2 = 1-2+3+4-5-6+7$$ $$4 = -1-2-3+4+5-6+7$$ $$6 = 1-2-3+4+5-6+7$$ $$8 = -1-2-3-4+5+6+7$$ $$10 = 1-2-3-4+5+6+7$$ $$12 = -1-2+3+4-5+6+7$$ $$14 = 1-2+3+4-5+6+7$$ $$16 = -1-2-3+4+5+6+7$$ $$18 = 1-2-3+4+5+6+7$$ $$20 = 1+2+3-4+5+6+7$$ $$22 = -1-2+3+4+5+6+7$$ $$24 = 1-2+3+4+5+6+7$$ $$26 = -1+2+3+4+5+6+7$$ $$28 = 1+2+3+4+5+6+7$$

$\endgroup$
4
  • $\begingroup$ I counted 67 solutions, in your answer 29. $\endgroup$
    – Nick
    Commented May 17, 2020 at 12:07
  • $\begingroup$ @Nick, I know! Please look at left column and text paragraph ;) $\endgroup$
    – JKHA
    Commented May 17, 2020 at 12:10
  • $\begingroup$ @Nick There are $2^7=128$ ways to set the +/- options. How do you count 67? $\endgroup$ Commented May 17, 2020 at 12:25
  • $\begingroup$ @danielmathias, you are right. I was disappointed by last sentence from the Ramillies's answer. $\endgroup$
    – Nick
    Commented May 17, 2020 at 12:58
-1
$\begingroup$

28 just 1 way 1+2+3+4+5+6+7=28 27 is 2 ways 2+3+4+5+6+7=27 1+2+3+4+5+6+7-1=27 26 is 3 ways 1+3+4+5+6+7=26 2+3+4+5+6+7-1=26 1+2+3+4+5+6+7-2=26 Like thak you can create all...

$\endgroup$
1
  • $\begingroup$ You don't use all numbers for odd sums. $\endgroup$
    – Nick
    Commented May 24, 2020 at 11:21

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