27

I'm reading a book about combinatorics. Even though the book is about combinatorics there is a problem in the book that I can think of no solutions to it except by using number theory.

Problem: Is it possible to put $+$ or $-$ signs in such a way that $\pm 1 \pm 2 \pm \cdots \pm 100 = 101$?

My proof is kinda simple. Let's work in mod $2$. We'll have:

$\pm 1 \pm 2 \pm \cdots \pm 100 \equiv 101 \mod 2$ but since $+1 \equiv -1 \mod 2$ and there are exactly $50$ odd numbers and $50$ even numbers from $1$ to $100$ we can write:

$(1 + 0 + \cdots + 1 + 0 \equiv 50\times 1 \equiv 0) \not\equiv (101\equiv 1) \mod 2$ which is contradictory.

Therefore, it's not possible to choose $+$ or $-$ signs in any way to make them equal.

Now is there a combinatorial proof of that fact except what I have in mind?

user66733
  • 7,379
  • 3
    A standard problem often classified as combinatorics is that the number of people who shook hands with an odd number of people is even. This one uses much the same idea. – André Nicolas Aug 28 '13 at 22:41
  • @AndréNicolas: If you already have the proof in your mind, would you please post a proof of my problem using the handshaking lemma? – user66733 Aug 28 '13 at 22:49
  • 3
    Frankly, I like your proof better than any of the answers. – asmeurer Aug 29 '13 at 04:48
  • 2
    Another way of phrasing your own solution: We consider the sum of 100 numbers, 50 odd ones and 50 even ones. That will be an even sum. Negating a number (changing sign from $-$ to $+$ or from $+$ to $-$) does not change its parity (its being odd or even). – Jeppe Stig Nielsen Aug 29 '13 at 09:43
  • @AndréNicolas: I haven't chosen the best answer yet because I'm still waiting for your answer based on the handshaking Lemma. If you have such a proof in mind please post it, because I'm really interested in it and it sounds like the most combinatorial solution to me. – user66733 Aug 31 '13 at 02:55
  • It is not worthwhile, Brian M. Scott's answer is better, and pretty combinatorial. – André Nicolas Aug 31 '13 at 02:57
  • @AndréNicolas: Well, at least let me know the proof, even if it's not better than Brian M. Scott's answer. – user66733 Aug 31 '13 at 02:58

5 Answers5

29

You can rephrase essentially the same argument in the following terms:

Suppose that there were such a pattern of plus and minus signs. Let $P$ be the set of positive terms, and let $N$ be the set of negative terms together with the number $101$. Then $\sum P-\sum N=0$, so $\sum P=\sum N$, and $\{P,N\}$ is a partition of $\{1,2,\ldots,101\}$ into two sets with equal sum. But $\sum_{k=1}^{101}k=\frac12\cdot101\cdot102=101\cdot51$ is odd, so this is impossible.

Brian M. Scott
  • 616,228
9

Another answer that use almost the same idea: the sum or subtraction of two even or odd number is an even number. How many odd number we have?

3

If $T_n=n(n+1)/2$ is the $n^{th}$ triangular number, an inductive proof (using $T_n+(n+1)=T_{n+1}$) shows the attainable numbers at step $n$ are $$-T_n,\ -T_n+2,\ \cdots , T_n-2, \ T_n,$$ in particular they all have the same parity as $T_n$. Since $T_{100}=5050$ is even, we see that $101$ cannot be attained in any way by $100$ steps.

addendum: The first triangular number at least $101$ is $T_{14}=105$ (and is odd). This overshoots the goal $101$ by $4$, so if we take the sum $$1+2+3+\cdots+14=105$$ and change the sign on the $2$, we get $101$. Seems this is the only way to get $101$ in 14 steps, and we cannot get it with 13 or fewer since $T_{13}=91$ is the largest with $13$ steps.

coffeemath
  • 29,884
  • 2
  • 31
  • 52
3

Replacing 100 with $n$ and using Brian M. Scott's solution, we want a partition of $\{1, 2, ..., n+1\}$ into two sets with equal sums.

The sum is $\frac{(n+1)(n+2)}{2}$, and if $n=4k$, this is $(4k+1)(2k+1)$ which is odd and therefore impossible.

If $n = 4k+1$, this is $(2k+1)(4k+3)$ which is also odd, and therefore impossible.

If $n = 4k+2$, this is $(4k+3)(2k+2)$, so it is not ruled out, and each sum must be $(4k+3)(k+1)$.

if $n = 4k+3$, this is $(2k+2)(4k+5)$ which is also not ruled out, and each sum must be $(k+1)(4k+5)$.

Now I'll try to find a solution for the not impossible cases. (I am working these out as I enter them.)

For the $n=4k+2$ case, the sum must be $(4k+3)(k+1) =(4k+4-1)(k+1) =4(k+1)^2-(k+1) =(2k+2)^2-(k+1) $. The square there suggests, to me, the formula for the sum of consecutive odd numbers $1+3+...+(2m-1)=m^2$, so $1+3+...+(4k+3) = (2k+2)^2$. If $k+1$ is odd, remove it from the sum so it is $(2k+2)^2-(k+1)$. If $k+1$ is even, both $1$ and $k$ are odd, so remove them from the sum. In either case, we have the desired partition.

For the $n=4k+3$ case, the sum must be $(4k+5)(k+1) =(4k+4+1)(k+1) =4(k+1)^2+(k+1) =(2k+2)^2+(k+1) $. Again, $1+3+...+(4k+3) = (2k+2)^2$. If $k+1$ is even, add it to the sum so it is $(2k+2)^2+(k+1)$. If $k+1$ is odd, $k+2$ is even, so remove $1$ and add $k+2$ to the sum. In either case, we have the desired partition.

I do not know if these partitions are unique.

marty cohen
  • 107,799
0

Consider both sides modulo $2$. Then the right side is $1$, whereas the left side is $0$ (since it consists of $50$ ones and $50$ zeros).

pre-kidney
  • 30,223