×

# Proof note - Combinatorics

Prove that the operators $$+$$ and $$-$$ cannot be chosen such that :

$$\quad$$

$$\pm1 \pm 2 \pm 3 \dots \pm 100 = 101$$

Note by Arian Tashakkor
2 years ago

Sort by:

Firstly,suppose all the operators are chosen as $$+$$ sign.That gives a total sum of 5050 which is an even number.Now changing each $$+$$ to a $$-$$ an even amount is reduced from the total sum and hence , the sum always remains an even integer!(for example consider changing $$+3$$ to $$-3$$ , the sum is reduced by $$2\times3=6$$) · 2 years ago

Separate the sum into evens and odds. Any number of evens, regardless of the parities, will and to an even number.

Any two odds, regardless of parity, will add to an even number. Now the sum has $$50$$ odd numbers, so we can form $$25$$ pairs of odds in any of$$\frac{50!}{2^{25}}$$ ways. Whichever way we do this, we will have $$25$$ even numbers as a result, which of course add to an even number, again regardless of parity.

Thus the given sum, with whatever operators we choose, must be even, and hence can never result in a sum of $$101.$$

The next question to ask is: how many distinct values can be achieved from the given (variable) sum? · 2 years ago

Well done sir!But I think you overcomplicated things a little bit. As a sequel challenge, could you provide a nicer and easier proof? And BTW I'll start working on your challenge first thing in the morning. · 2 years ago

Suppose there is, then there is a signed sum of 50 odd numbers and 50 even numbers that adds up to 101. But that's impossible by parity because $$\text{LHS} \equiv 0 \bmod 2$$ while $$\text{RHS} \equiv 1 \bmod 2$$. · 2 years ago

Nice job sir!You said what I had in mind ... well,rather "formally" though. xD . I post my own solution.Would you mind checking it out for me please? Thanks in advance. · 2 years ago

A sum of n integers can be odd only when there are odd number of odd numbers in it.

Here there are 50 odd numbers.

So regardless of signs this can never be odd. · 2 years ago