Strange Sum of numbers $1$ to $100$

Question

I came across this problem the other day. It is as follows:

The strange sum is as follows. Starting at the any term in a set, when the next term is added to the 'tally', the second term is subtracted from the first if the result is nonnegative, otherwise it is added to the tally. Then the third term is subtracted from the strange sum if the result is nonnegative, otherwise it is added to the 'strange sum'. Repeat the process. For example, the 'strange sum' of the sequence $1, 3, 4, 2, 5$ is $1+3-4+2+5=7$

Suppose there is a list of numbers from $1$ to $100$ in some order. What is the largest possible 'strange sum'?

I couldn't find any clear pattern. However, I did notice that if the sum of the first $99$ terms is $99$, then $100$ can be added, hence making the total sum $199$. Any thoughts on this problem?

(edit) I just realised that $199$ is impossible as the sum of the first $99$ natural numbers is even and so it would be impossible to achieve a 'strange sum' of $99$. That would mean that $198$ is the next highest possibility. $98$ is achievable via the 'strange sum' by the first $99$ natural numbers in some order, though I still have not been able to constitute a proof for $198$.

Answer 1

Well you can't reach $199$, but you can reach $198$. I'll prove both:

In order to reach $199$, we need to reach $0$ with the first $98$ numbers.

But $\dfrac {98(98+1)}2=49\times 99$ is odd, so you can't split the list $\{1,\dots,98\}$ into 2 parts with equal sum.

[EDIT2: An easier way to see this is to notice the parity of the odd sum and $1+2+\dots+100$ must be the same; changing signs do not change the parity.]

Here is a way to reach $198$: $(1,96,2,95,\dots,48,49,97,99,98,100)$

The first $96$ numbers cancel out. $97+99-98+100=198$.

EDIT: To see the relation to A047415, we consider this:

If the sum of the first $(n-2)$ numbers is even, we can split the first $(n-2)$ numbers into two parts of equal sum. Manipulating the order of our sum will give $0$, so we can reach $(n - 1) + 1 = 2n-1$.

If the sum of the first $(n-2)$ numbers is odd, the sum of the first $(n-4)$ numbers is even. We can split the first $(n-4)$ numbers into two parts of equal sum. Manipulating the order of our sum will give $0$, so we can reach $(n-3)+(n-1)-(n-2)+n=2n-2$.

For $n = 4k+r$, the sum of the first $(n-2)$ numbers is $\dfrac {(n-2)(n-1)}2 = \dfrac {(4k+r-2)(4k+r-1)}2$, which is even for $r=1,2$, odd for $r=0,3$.

Hence: $$4k\mapsto 8k-2$$$$4k+1\mapsto 8k+1$$$$4k+2\mapsto 8k+3$$$$4k+3\mapsto 8k+4$$

which is $1,3,4,6 \pmod 8$, in that order.