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
- Is this conjecture true?
- If so, what does the proof look like?
- Is this a tired old chestnut that we should have known?
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$.