25
$\begingroup$

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?

$\endgroup$
  • 3
    $\begingroup$ 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. $\endgroup$ – André Nicolas Aug 28 '13 at 22:41
  • $\begingroup$ @AndréNicolas: If you already have the proof in your mind, would you please post a proof of my problem using the handshaking lemma? $\endgroup$ – user66733 Aug 28 '13 at 22:49
  • 3
    $\begingroup$ Frankly, I like your proof better than any of the answers. $\endgroup$ – asmeurer Aug 29 '13 at 4:48
  • 2
    $\begingroup$ 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). $\endgroup$ – Jeppe Stig Nielsen Aug 29 '13 at 9:43
  • $\begingroup$ @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. $\endgroup$ – user66733 Aug 31 '13 at 2:55
27
$\begingroup$

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.

$\endgroup$
9
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.