Странная сумма чисел $1$ к $100$

Question

Я столкнулся с этой проблемой на днях. Это выглядит следующим образом:

Странная сумма такова. Начиная с любого члена в наборе, когда следующий член добавляется к «счету», второй член вычитается из первого, если результат неотрицательный, в противном случае он добавляется к счету. Затем третий член вычитается из странной суммы, если результат неотрицательный, в противном случае он добавляется к «странной сумме». Повторите процесс. Например, «странная сумма» последовательности$1, 3, 4, 2, 5$ является $1+3-4+2+5=7$

Допустим, есть список номеров из $1$ к $100$в каком-то порядке. Какая самая крупная «странная сумма»?

Я не мог найти четкого рисунка. Однако я заметил, что если сумма первых$99$ условия $99$, тогда $100$ может быть добавлен, следовательно, общая сумма $199$. Есть мысли по этой проблеме?

(править) Я только что понял, что $199$ невозможно как сумма первых $99$ натуральные числа четны, поэтому было бы невозможно получить "странную сумму" $99$. Это означало бы, что$198$ следующая наивысшая вероятность. $98$ достижимо через «странную сумму» по первому $99$ натуральные числа в некотором порядке, хотя я до сих пор не смог доказать $198$.

Answer 1

Ну ты не можешь добраться $199$, но вы можете достичь $198$. Докажу оба:

Чтобы достичь $199$, нам нужно достичь $0$ с первым $98$ числа.

Но $\dfrac {98(98+1)}2=49\times 99$ странно, поэтому вы не можете разделить список $\{1,\dots,98\}$ на 2 части с равной суммой.

[РЕДАКТИРОВАТЬ2: Более простой способ увидеть это - заметить четность нечетной суммы и $1+2+\dots+100$должно быть таким же; изменение знаков не меняет четности.]

Вот способ добраться $198$: $(1,96,2,95,\dots,48,49,97,99,98,100)$

Первый $96$ числа отменяются. $97+99-98+100=198$.

РЕДАКТИРОВАТЬ: Чтобы увидеть связь с A047415, мы рассматриваем это:

Если сумма первых $(n-2)$ числа четные, мы можем разделить первые $(n-2)$числа на две части равной суммы. Манипулирование порядком нашей суммы даст$0$, так что мы можем достичь $(n - 1) + 1 = 2n-1$.

Если сумма первых $(n-2)$ числа нечетные, сумма первых $(n-4)$числа четные. Мы можем разделить первое$(n-4)$числа на две части равной суммы. Манипулирование порядком нашей суммы даст$0$, так что мы можем достичь $(n-3)+(n-1)-(n-2)+n=2n-2$.

За $n = 4k+r$, сумма первых $(n-2)$ числа $\dfrac {(n-2)(n-1)}2 = \dfrac {(4k+r-2)(4k+r-1)}2$, что даже для $r=1,2$, странно для $r=0,3$.

Отсюда: $$4k\mapsto 8k-2$$$$4k+1\mapsto 8k+1$$$$4k+2\mapsto 8k+3$$$$4k+3\mapsto 8k+4$$

который $1,3,4,6 \pmod 8$, в этой последовательности.