задачка (математическое)

[avva]

В рабочую рассылку прислали хорошую задачку.

У вас есть пять целых чисел N1, N2, N3, N4, N5. Вы повторяете следующую операцию: выбираете какое-нибудь отрицательное среди них, меняете его знак с минуса на плюс, и вычитаете его положительное значение из обоих его соседей. Например, если у вас есть [10, 5, -4, -8, 2] и выбрали -4, то получится [10, 1, 4, -12, 2]. У крайних чисел один из соседей берется с второго края (так, соседи N1 - N2 и N5). Обратите внимание, что сумма всех чисел после этой операции не меняется.

Дано, что вначале сумма всех чисел положительна. Доказать или опровергнуть: невзирая на то, как выбираются числа, после конечного числа операций отрицательных чисел не останется.

Комменты не скрываются.

Comments

[avva.livejournal.com]

I can now prove that a negative-sum game will diverge. This follows
immediately from a stronger claim that I'll need for the positive-sum
later:

Lemma 3. In a negative-sum positive-direction game, given a tuple with
a minimal number -M, M > 0 (the minimal number is negative because
the game is negative-sum), the game will produce a tuple with a number
less than M in no more than K steps, where K depends only on the total
sum and not on the particular tuple or M.

Proof. The game cannot stop at all - the sum is negative so there'll
always be a negative number. The game cannot continue long without
inverting either -M or one of its neighbors, using just the two
remaining slots, because that is identical to a 2-number no-wraparound
game, and this finishes in 3 steps by Lemma 1. So after 3 steps we'll
have to invert -M or its neighbors; inverting an neighbor will
decrease -M immediately so this is a trivial case; therefore we can
assume -M is inverted to M. If one of its neighbors is negative at the
time, it gets decreased to a number less than -M, and we're done too;
so we can assume that the tuple looks like this when inverting -M:

[x A -M B y] -> [x (A-M) M (B-M) y], here A,B,M are nonnegative and
the signs of x,y are uncertain. We also know that the total sum is
negative: x + A -M + B + y < 0.

We want to show that after a constant number of steps, we'll get two
neighbors with total sum less than -M; and then by the hanging-gun
lemma (Lemma 2) we're done.

A-M and B-M might both be positive; or they could be negative but we
might choose to invert x or y instead of either of them. But we can
only focus on x,y for a few steps (by Lemma 1), and every time we
invert x or y, we decrease one of (A-M), (B-M), and we can still
denote them (A-M), (B-M) after such a decrease, shifting A or B
appropriately. We can assume that A-M and B-M won't get less than -M
as a result of this (because otherwise we're done), so A,B remain
nonnegative. After no more than a few steps, we'll invert either A-M
or B-M - either out of choice or due to turning x,y nonnegative by
Lemma 1; the tuple at that point can still be represented as

[x (A-M) M (B-M) y], with A,B,M nonnegative, x,y uncertain

Suppose we invert A-M at this point, getting to [(x+A-M) (M-A) A (B-M)
y]. If B-M is positive, then B >= M; but B is the sum of the three
middle numbers in the tuple now, and since the total sum is < 0, the
sum of the edge numbers will be < -M, and we're done. So we can assume
B-M is negative just as A-M is, and rewrite the tuple, before
inverting A-M, as

[x -C M -D y], C, D, M nonnegative, C,D <= M, we're about to invert -C.

The next tuple we get is

[(x-C) C (M-C) -D y]

We now repeatedly show that any way to proceed will quickly lead us to
a triple of consecutive numbers with total sum >=M, so that the other
two numbers must have sum < -M, which is enough by the hanging lemma.
To start with, if we invert -D now, we get

[(x-C) C (M-C) -D y] -> [(x-C) C (M-C-D) D (y-D)],

and the sum of three middle numbers is M. So we can't invert -D. M-C
is nonnegative, so it's out. If x-C is negative, and we invert it, we
get

[(x-C) C (M-C) -D y] -> [(C-x) x (M-C) -D (y+x-C)],

and the sum of the first three numbers is M. The only remaining option
is to invert y, assuming it's negative, to get

[(x-C) C (M-C) -D y] -> [(x-C-y) C (M-C) (-D-y) y].

Now we have only one or two remaining negative numbers to invert -
(x-C-y), possibly, and (-D-y), certainly; and using either leads to a
triple summing to M:

[(x-C-y) C (M-C) (-D-y) y] --inverting (x-C-y)--> [(y+C-x) (x-y) (M-C)
(-D-y) y], first three numbers

[(x-C-y) C (M-C) (-D-y) y] --inverting (-D-y)--> [(x-C-y) C (M-C-D-y)
(D+y) y], middle three numbers

To sum all of this up, in the worst case, after 10 steps from the
initial tuple - three before we have to invert -M, one to invert -M,
three more before we have to invert one of its neighbors, one to
invert a neighbor, and three more to exhaust all possibilities after
that - we reach a situation where we can invoke Lemma 2 and conclude
that a number less than -M will be generated. This proves Lemma 3 and
the claim that a negative-sum game will diverge.

[avva.livejournal.com]

Lemma 4: A positive-sum positive-direction game will stop (the puzzle
as requested).

Proof: Let the sum of the initial tuple be S. We first prove that
there's an upper bound on the numbers appearing in the game, starting
from a given tuple. Suppose we played for N steps, and see a number M
in the tuple that's larger than all the numbers in previous tuples. If
we now start from the current tuple and reverse the arrow of time,
we'll be playing a positive-sum negative-direction game, with sum S.
But this game is equivalent, by inverting all numbers, to a
negative-sum positive-direction game with sum -S, with -M in the
starting tuple. By Lemma 3, after some K steps, where K depends only
on -S, we'll see a tuple with a number less than -M, or - inverting
back - larger than M. This is impossible if by going back K steps
we're still within the N steps we played in the original game, by the
maximality of M in it. So by choosing N larger than K, we can ensure
that we'll never see a new maximal champion after N steps.

Now we prove that the numbers must be bounded from below as well. If M
is a positive upper bound on all numbers in the game starting from a
given tuple, then any negative number -M', M' > M, that appears in the
game, must never be inverted again - it can only be further decreased.
That turns the remaining numbers into a 4-number no-wraparound game A,
B, C, D. In this game, inverting A or D increases the total sum, and
it's impossible to only keep inverting B and C (Lemma 1), so the total
sum keeps increasing. Yet it can't grow beyond 4M, because M is the
upper bound on everything in the enclosing 5-game; so the game must
stop, meaning A,B,C,D will be nonnegative and we'll have to invert
-M', contradicting the maximality of M. It follows that a negative
number -M' with M' > M cannot arise in the game, so that the game is
bounded by [-M, M].

Finally, the game cannot end in a cycle, because such a cycle becomes
a cycle in a negative-direction game (played from finish to start by
reversing the time), and this in turn becomes a cycle in a
negative-sum positive-direction game by inverting all numbers, and
this is impossible by Lemma 3.

The last claim, that given an initial sum of 0, the game goes into a
cycle, is a consequence of the above: because the sum is nonnegative,
the game is bounded, but it cannot stop at any nonnegative tuple
except [0,0,0,0,0].