Consider the following problem.

Is it possible to place signs,

plus and minus, before numbers one, two,three and so on until nine

and some of the resulting numbers up in such a way that

as a result we obtain the sum 100?

The second question, can we obtain the sum two, as a result?

Let us start with 100.

Note that the sum of these numbers is maximal if we place signs, plus, everywhere.

Let us do it and see what is the resulting sum in this case.

Let us place the plus signs here and the result is 45.

We can do the calculations and see that it is 45.

So, this is the maximal possible number we can obtain.

So, if we place some other signs there the sum will be even smaller.

So, 45 is the maximum and we cannot obtain 100 as a result.

Let us now proceed to the second question.

Can we get two as the sum of these sequence?

Here is the place where we would need to consider

properties of the numbers to be odd and even.

Is it possible to get two?

And the main observation here is that in the sequence,

there are five even numbers and five odd numbers and as a result,

no matter how we place signs there,

the sum will always be odd.

Because the sum of two odd numbers is even,

the sum of an even and an odd number is odd and the sum of two even numbers is even.

So, if you sum up five even numbers and five odd numbers,

it can be seen easily that the result will be always odd not matter how we put

the signs here and so, the sum two is impossible.

Let us also consider the more general question.

What are the possible sums we can get here?

Can we list all possible sums we can obtain

by placing the signs in this sequence?

We have two constrains, two obstacles.

We have shown that the sum is always odd,

we cannot obtain an even number as a sum

and we have also shown that the sum is at most 45.

The maximum possible sum is 45.

Symmetrically, if we place all signs to be minus, we obtain minus 45.

These are the constraints that we have and it turns

out that this is all constraints that are present here.

So all other sums are possible.

If some numbers satisfy both of the restrictions we have found then it is

possible to obtain it to place the signs in the right way such that

the sum is equal to this number.

We will not discuss it in

details but you can try to do it yourself.

It is not very complicated and to do it, you can consider the following greedy algorithm.

Let us consider this sequence of numbers,

one, two, three and so on until nine and

let's go from right to left and let's place signs gradually.

You have your current goal number and you have your current sum.

Initially the current sum was zero and then you place some sign before the number,

you add it or subtract it from your current sum.

If your current sum is less than the goal, you increased your current sum,

you place the sign plus and if the current sum

is greater than the goal or equal to the goal, let us place the sign minus.

It turns out that

this greedy algorithm always gives you the right sequence of signs,

plus and minus, and it can be shown

using some other invariant that we have not considered for this problem yet,

so you can try to think about it yourself.