Waste less time on Facebook — follow Brilliant.

Proof note - Combinatorics

Prove that the operators \(+\) and \( - \) cannot be chosen such that :


\(\pm1 \pm 2 \pm 3 \dots \pm 100 = 101\)

Note by Arian Tashakkor
2 years, 2 months ago

No vote yet
1 vote


Sort by:

Top Newest

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\)) Arian Tashakkor · 2 years, 2 months ago

Log in to reply

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? Brian Charlesworth · 2 years, 2 months ago

Log in to reply

@Brian Charlesworth 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. Arian Tashakkor · 2 years, 2 months ago

Log in to reply

@Arian Tashakkor 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 \). Pi Han Goh · 2 years, 2 months ago

Log in to reply

@Pi Han Goh 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. Arian Tashakkor · 2 years, 2 months ago

Log in to reply

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. Chandrachur Banerjee · 2 years, 2 months ago

Log in to reply


Problem Loading...

Note Loading...

Set Loading...