2
$\begingroup$

While supervising a student competition, my colleague and I ran across an interesting problem. Deobfuscated, it boils down to this

Given a limit value $M$, which integers in the range $1,\dotsc,M-1$ can be represented as a sum of consecutive odd numbers or their negatives, starting at $1$?

The requirement is: represent a number in the above range as $$ \sum_{i=0}^L(\pm)(2i + 1) $$ for some upper limit value $L$. We also have the restriction that each prefix sum must be in $1,\dotsc,M-1$, namely $$ 1\le\sum_{i=0}^k(\pm)(2i + 1)< M $$ for all $0\le k \le L$.

For example, if $M = 17$ we can have sums $1, 2, 4, 7, 9, 11, 16$, since, for example $11=1+3+5-7+9$.

We conjecture that for $M\ge 50$ [Edit: was 46, but I missed some cases], any target sum $1\le s< M$ is possible, which brings me to the questions

  1. Is this conjecture true?
  2. If so, what does the proof look like?
  3. Is this a tired old chestnut that we should have known?
$\endgroup$
5
  • $\begingroup$ Do the individual odd numbers you're adding or subtracting need to be each no greater than $M$? $\endgroup$ – John Nov 13 '14 at 22:26
  • $\begingroup$ Yes, because at each step the prefix sum property assures us that the sum so far is in $[1, M-1]$. That being the case, adding a number $M-1$ or greater would push you out of range. $\endgroup$ – Rick Decker Nov 14 '14 at 0:48
  • $\begingroup$ I've edited the question to explain it in more detail. I hope it clarifies things. $\endgroup$ – Rick Decker Nov 14 '14 at 0:55
  • $\begingroup$ By "prefix sum" do you mean "partial sum?" $\endgroup$ – Akiva Weinberger Nov 14 '14 at 1:02
  • $\begingroup$ @columbus8myhw. Sure. $\endgroup$ – Rick Decker Nov 14 '14 at 1:05
0
$\begingroup$

I'm not sure if I got the question since you should be able to make more numbers with $M=17$ for example $3=1-3+5$ but since I don't have enough rep to ask I'll just post an answer and if I'm answering some different problem you'll let me know and I'll fix it :)

I would argue that this is a tired old chestnut since you are effectively just looking at how far away numbers are from squares. Although it has a pleasant twist to it.

So basically since the squares you have access too are $1,4,9, \dots 484$ since the highest number you get to use is $45$. You have to make sure that all numbers from $1$ to $46$ are atleast $r<90$ smaller than one of our squares where $r$ is an even number. This means that we only need to worry about elleven squares since $11^{2}=121<46+90<144=12^{2}$.

OK so lets construct a method that finds the smallest bigger square than some number with an even distance. Right off the bat we notice:

$1$, Square
$-1+3=2$, $r=2$
$1-3+5=3$, $r=6$
$1+3 = 4$, Square
$1-3+5-7+9= -1+3+5+7-9=5$, $r=20$ Should be $r=4$ but that is not possible!

that when our $r$ has a power of two we will need to turn as many plusses into minuses as the power*, this means that we will need more numbers and that our $k$ will grow large. Since the largest number we're allowed to use is $45$ our $k$ can not grow larger than $22$, how big a $k$ do we need for the $r$ that has the largest power of two in our sequence?

(* When you change one plus into minus you change the sum by $2j$ where j is the variable you changed the symbol on. If you need to change the sum by $j=2^{y}*p$ then you need to change $y$ plusses.)

Since $x^{2}$ is a convex fucntion it is evident - if we ignore the power of two rule we discovered for a second - that $r$ is the biggest right after a square since then it has the longest way to go to the next square. This means that we need to look at the odd numbers from $27$ to $45$ and the even numbers from $38$ to $46$ and find the highest power of two on the way to $49$ (whose sum has $7$ terms) and $64$ (whose sum has $8$ terms) respectively. $$ 49-27 = 22 < 32 \\ 64-38 = 26 < 32 $$ The lowest number that produces the highest power of two is therefore $49-16=33$. To create 33 we need to change 4 plus signs that will lower the sum by atleast $2\cdot 4^{2}=32$. So we need a higher square, the next square has $r=81-33=48$ which means we just need to change the signs on $3,\; 5,\; 7$ and $9$ to accomplish our goal.

So that shows that the sums are possible for $46$. What is the lowest possible $M$?

Well since $x^{2}$ is convex we're basically trying to find when this first starts to happen and then it should be true for every $M>M_{0}$. From our earlier example we can see that we will need to atleast try for $M=9$.

$6$, $r=10$
$7$, $r=2$
$8$, $r=8$ doesn't work so we need $r=28$ the sequence is $1+3-5+7-9+11$.

So now we need to go to $M=11$

$9$, Square
$10$, $r=6$
$11$, $r=14$

So I'd guess $M=11$ is the smallest $M$.

$\endgroup$
4
  • $\begingroup$ "For example, if M=17 we can have sums 1,2,4,7,9,11,16, since, for example 11=1+3+5−7+9" Since you could ignore the 1+3+5+7+9 = 25 > M sum I assume that you just need to be able to build all the numbers from 1 and to M you don't need all the possible sums to be in that range (then this is quite clearly impossible). $\endgroup$ – Pawnda Nov 14 '14 at 3:02
  • $\begingroup$ $1-3+5$ violates the condition that all partial (prefix) sums need to lie in the range $1\leqslant \sum_{i=0}^k \pm(2i+1) < M$, the second partial sum $1-3 = -2 < 1$ is out of range. The first time you can possibly use $-(2i+1)$ is at $i = 3$, when $1+3+5-7 = 2 \geqslant 1$. $\endgroup$ – Daniel Fischer Nov 14 '14 at 11:21
  • $\begingroup$ Ah ok I thought you could pick the plusses and minuses for each k so since k=3 there and the end result is within range its allowed. For k=2 I would pick in a different way to satisfy the rule etc. Ok I'll change this when I get time $\endgroup$ – Pawnda Nov 14 '14 at 11:42
  • $\begingroup$ For example, if $M\ge 10$ you could have $2=1+3+5-7$ and if $M\ge 36$ you could also have $2=1+3+5+7+9-11+13-15+17-19+21-23+25-27+29-31+33-35$ $\endgroup$ – Rick Decker Nov 14 '14 at 19:43

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.