Proof note - Combinatorics

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

$\quad$

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

#Combinatorics #NumberTheory #Operation

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.
Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

Markdown	Appears as
`italics` or `_italics_`	italics
`bold` or `__bold__`	bold
- bulleted - list	bulleted list
1. numbered 2. list	numbered list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1 paragraph 2	paragraph 1 paragraph 2
`[example link](https://brilliant.org)`	example link
`> This is a quote`	This is a quote
# I indented these lines # 4 spaces, and now they show # up as a code block. print "hello world"	# I indented these lines # 4 spaces, and now they show # up as a code block. print "hello world"

Math	Appears as
Remember to wrap math in `$` ... `$` or `\[` ... `\]` to ensure proper formatting.
`2 \times 3`	$2 \times 3$
`2^{34}`	$2^{34}$
`a_{i-1}`	$a_{i-1}$
`\frac{2}{3}`	$\frac{2}{3}$
`\sqrt{2}`	$\sqrt{2}$
`\sum_{i=1}^3`	$\sum_{i=1}^3$
`\sin \theta`	$\sin \theta$
`\boxed{123}`	$\boxed{123}$

Comments

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 - 6 years ago

Separate the sum into evens and odds. Any number of evens, regardless of the parities, will add 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 - 6 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.

Arian Tashakkor - 6 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$ .

Pi Han Goh - 6 years ago

@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 - 6 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.

Chandrachur Banerjee - 6 years ago

Math	Appears as
Remember to wrap math in `\(` ... `\)` or `\[` ... `\]` to ensure proper formatting.
`2 \times 3`	$2 \times 3$
`2^{34}`	$2^{34}$
`a_{i-1}`	$a_{i-1}$
`\frac{2}{3}`	$\frac{2}{3}$
`\sqrt{2}`	$\sqrt{2}$
`\sum_{i=1}^3`	$\sum_{i=1}^3$
`\sin \theta`	$\sin \theta$
`\boxed{123}`	$\boxed{123}$