2

If I have an positive integer $x \in \mathbb{N}$ and I have $Z = \sum_{i = 0}^{n}{i}$ such that $Z \geq x$ and $Z - x \equiv 0 \bmod 2$ and $n$ is the smallest such integer it is possible to create and alternating sum from $1 \ldots n$ such that it equals $x$.

For example:

Say $x = 11$, then $Z = 15$ and $n = 5$ and the sum is $1 - 2 + 3 + 4 + 5$.

I see why the condition is necessary I don't see why it is sufficient.

NasuSama
  • 3,364
Daniel Papp
  • 23
  • When you write "alternating sum", you don't actually mean (strictly) alternating, do you --- just that you're allowed both plus and minus signs. – Gerry Myerson May 12 '13 at 13:15
  • Yes. I couldn't really come up with a better name for it. – Daniel Papp May 12 '13 at 13:20
  • It is related to the solution of this code jam problem -> http://code.google.com/codejam/contest/2437488/dashboard#s=p1 and also I don't have the slightest idea how to approach this. – Daniel Papp May 12 '13 at 13:48

2 Answers2

1

Check that this is true for $n \le 2$ (which implies $x=0,1,3$)

Then, proceed by induction : first do the $+n$ jump. Then you are left with jumps of length $1 \ldots n-1$ and you are trying to move by $|x-n|$. Since $|x-n| \equiv x-n \equiv 1+2+ \ldots +n-n = 1+2+ \ldots + (n-1) \pmod 2$ and $|x-n| \le \max (n, x-n) \le \max (n, 1+2+\ldots+(n-1)) \le 1+2+\ldots+(n-1)$, you can apply the inductive hypothesis (or use recursion, programmatically)

mercio
  • 50,180
0

Let $S(n)=\{x:x=\pm1 \pm2 \cdots \pm n\}$.
Let $T(n)=\{x:|x|\le \frac{n(n+1)}{2}\}\cap\{x:x\equiv \frac{n(n+1)}{2}\pmod{2}\}$.

Claim: $S(n)=T(n)$ for all $n\in \mathbb{N}$.
Proof: Induction on $n$. $n=1,2$: clear
$S(n+1)\subseteq T(n+1)$: consider all $+$ or all $-$
$T(n+1)\subseteq S(n+1)$: $$[0,\frac{(n+1)(n+2)}{2}]\subseteq[-\frac{n(n+1)}{2}+n,\frac{n(n+1)}{2}+n]$$ and $$[-\frac{(n+1)(n+2)}{2},0]\subseteq[-\frac{n(n+1)}{2}-n,\frac{n(n+1)}{2}-n]$$

Now, let $ x\in T(n+1)$ and $x\equiv \frac{(n+1)(n+2)}{2}\pmod{2}$. By the above pair of inclusions, either $x+n$ or $x-n$ is in $T(n-1)$. But also $\frac{(n+1)(n+2)}{2}- n =\frac{n^2+3n+2- 2n}{2}\equiv \frac{n^2+n+2}{2}\equiv \frac{n(n+1)}{2} \pmod{2}$. [and $n\equiv -n\pmod{2}$]. Hence we're done by the inductive hypothesis.

vadim123
  • 82,796