Ни о какой безапелляционности в моих высказываниях не может быть и речи!

a na kursah po linejnoj algebre kak demonstracija pol'zy diagonalizacii matricy. I esche, kazhetsja, est' para nauk gde ona iljustriruet chto-to svoe :)

From:

мне не очень ясно, как здесь помогает диагонализация матрицы - можешь рассказать?

From:

сорри, я как обычно поторопился и не вчитался в формулировку. Про диагонализацию другая задача, где содержимое регистра делится пополам между соседними, причем все это одновременно по всем регистрам
(задача о жадинах и манной каше). А эта задача (с моей точки зрения) -- про группы порожденные отражениями, конкретно про аффинную группу Вейля типа А.

From:

PS let me know if you're interested in details

From:

I am! Как раз собирался попросить.

From:

Well, I'll try to be brief. First, if the sum of the 5 numbers is zero, your transformations generate
a finite group, namely the group S_5 of permutations on 5 letters -- this is easy to see by choosing auxiliary coordinates y_1, .., y_5, so
that x_i = x_{i+1}-x_i, x_5=y_1-y_5, then the change
of x's you described corresponds to switching a pair
of neighboring y's. Geometrically one can think of it as a group generated by reflections in the hyperplanes y_i=y_j. Replacing 5 by 3 we would get 3 lines intersecting at 60 or 120 degrees partitioning the plane in 6 regions. Those regions
for a general n (instead of 3,5) are called (Weyl) chambers.
A standard thing to do with a sequence of numbers is to change the order "locally" interchanging two neighbors (where at the moment "neighborhood" is understood non-cyclically, so y_1 and y_5 aren't neighbors)
appearing in a "wrong" order, after a few steps
the sequence necessarily becomes monotone.
Geometrically this corresponds to reflecting a point in a Weyl chamber at a hyperplane bounding the chamber and separating it from the standard chamber (the latter consists of points with x_i>0,
y_i monotone). This gets the point closer (in some sense) to the standard chamber and eventually into it.
Now, your problem is about an "affine" version of this. For non-zero sum the group is an infinite but still discrete group of affine-linear transformations of the 4-space, in fact it's isomorphic to the semi-direct product of S_n and a group of translations. The role of chambers is played by
alcoves, with 5 replaced by 3 these are members in the tesselation of the plane by equilateral triangles,
see e.g. the "A_2" picture at
http://www.math.ubc.ca/~cass/coxeter/r.html

Again, each transformation you describe takes
the point closer to the "fundamental alcove"
(where all x_i are positive) and eventually into it.
One can rewrite this argument algebraically -- say, using y_i such that x_i = y_{i+1}-y_i, though now we'll have to have y_i indexed by all integers, with y_{i+5}=y_i+s, where s is the sum of x_i's.
But then things get less intuitive.

From:

PS I meant the "Affine A2" picture.

From:

First, if the sum of the 5 numbers is zero, your transformations generate
a finite group, namely the group S_5 of permutations on 5 letters -- this is easy to see by choosing auxiliary coordinates y_1, .., y_5, so
that x_i = x_{i+1}-x_i, x_5=y_1-y_5, then the change
of x's you described corresponds to switching a pair
of neighboring y's.

I lost you here. E.g. if my x's are

[1 1 1 1 -4]

then the list of y's, the differences, is

[0 0 0 -5 5]

Now if I apply the transformation to -4 in the original list, I get:

[1 1 1 1 -4] -> [-3 1 1 -3 4]

with the list of differences

[4 0 -4 7 -7]

which isn't a permutation of [0 0 0 -5 5] at all. Am I missing something?

From:

no, no, it's the other way around -- your x's are differences of my y's (I had a typo in my text, sorry). In your example we can take
(0,1,2,3,4) for y's. Permuting I get
(4,1,2,3,0) with the list of differences
(-3,1,1,-3,4).
In fact, the algebraic argument is also short (even if less intuitive), here it is.
Choose y_i for all integer i, s.t. x_i=y_{i+1}-y_i
for i=1,..,5, and y_{i+5}=y_i+s, where s is the sum of x_i's. Since s is positive, the total number of disorders, i.e. of pairs i,j, s.t. iy_j, modulo
the change (i,j) \to (i+5k,j+5k), is finite.
The transformation you describe amounts
to swapping y_{i+5k} with y_{i+1+5k} for some
i s.t. y_i>y_{i+1}. It decreases the number of disorders by 1, so after a finite number of steps
the sequence of y's will be monotone, and the sequence of x's won't have negative terms.
Of course, integrality of x's is irrelevant.

From:

Применение правила к (2,0,0,0,-1) дает (1,0,0,-1,1). Для y'ков получим соответственно (2,2,2,2,1) и (1,1,1,0,1), что не является перестановкой....

From:

ja zh govorju, tot variant procedury, chto vy tut pytaetes' ispol'zovat', rabotaet tol'ko esli summa x'ov ravna nulju, potomu chto dlja nego nuzhno chtoby x_1=y_2-y_1, x_2=y_3-y_2, ... , x_5=y_1-y_5.

Dlja vashih x'ov nado brat' beskonechnuju v obe storony posledovatel'nost' y'ov: ..., 2,2,2,2,1,3,3,3,3,2, ...
takaja posl-t' budet perestavljat'sja.

From:

Ни разу не видел. Странно, при чем тут CS - задачка чисто математическая.

From:

vodianoj.livejournal.com

Вроде бы очевидно, что если сумма всех пяти чисел меньше нуля, и как ты показал, после каждой операции она не меняется, то это значит, что всегда останется хотя бы одно отрицательное число.

From:

-1 2 3 4 5 => 1 1 3 4 4

From:

meshko.livejournal.com

Нет, речь о том, что есть конфигурации, которые очевидно не сойдутся к всем неотрицательным.
Типа
-1 -1 -1 -1 -1

From:

vodianoj.livejournal.com

-1 + 2 +3 +4 +5 > 0

From:

vodianoj.livejournal.com

А да я уже вижу.

From:

meshko.livejournal.com

Дано, что вначале сумма всех чисел положительна.

From:

spamsink.livejournal.com

Поступим наоборот - докажем, что если брать положительное число, которое всегда найдется, прибавлять его к соседям и инвертировать, то в цикл войти не удастся. Для этого покажем, что максимальное положительное число в процессе этой процедуры растет, пусть и не монотонно. Рассмотрим единственный нетривиальный случай - когда мы берем максимальное положительное число M и оба его соседа отрицательны:
x -a M -b y
(знак x и y неизвестен, но M-a-b+x+y > 0).
Тогда первым шагом получаем
х M-a -M M-b y
Дальше рассматриваем все комбинации знаков x и y, и выясняем, что не более чем через 4 шага у нас останутся рядом два положительных числа, в сумме больших M, отчего на следующем шаге максимум возрастет. ЧТД.

From:

Здорово! Я почти до этого дошел, пытаясь обобщить легкий случай с тремя числами, но запутался где-то в комбинации знаков. Собственно, еще и не распутался, надо перепроверить.

Однако это одновременно не совсем верно ("на следующем шаге максимум возрастет" - но следующий шаг не обязан использовать одно из этих чисел), и недостаточно: это доказывает, что в исходной процедуре нет цикла, но не доказывает, что невозможно, чтобы числа по модулю продолжали расти неограниченно.

Кажется, для решения обеих проблем нужен небольшой шажок: показать по индукции, что если - пользуясь обратной процедурой, меняющей положительные на отрицательные - рядом стоят положительные a,b, то не позднее какого-то фиксированного числа шагов, зависящего только от суммы всех чисел (! но не от самих чисел, это важно), появится положительное число не меньше a+b.

Если это верно, и число шагов равно например K, то при использовании обычной процедуры максимальное положительное число должно быть достигнуто не более чем за K+4 шага от начала, иначе мы сможем обратить время и получить еще большее число, опровергая его максимальность. Значит, и максимальное отрицательное число должно появиться за это время, и поэтому все числа ограничены, а раз циклов нет, процедура останавливается.

Чтобы эту лемму доказать, достаточно смотреть на три оставшиеся числа и показать, что на них крутиться можно только конечное число шагов, зависящее от общей суммы. Т.к. использование только одного из них не задевает a,b, а остальные задевают и увеличивают a либо b, через конечное число шагов, зависящее от общей суммы, сумма трех оставшихся будет отрицательной; но задача с отрицательной суммой и обратным движением эквивалентна задаче с положительной суммой и обычным движением (с несущественным изменением "потери" части суммы в a,b при каждом шаге), и из случая для трех чисел ясно, что она окончится - опять таки за число шагов, зависящее от общей суммы.

From:

selfmade.livejournal.com

По-моему просто. Если сумма всех чисел больше нуля, то не останется отрицательных, а если меньше нуля - то положительных. Постепенно всё сойдётся к среднему арифметическому.

From:

kalvado.livejournal.com

после каждого шага появляется положительное число, так что ко всем отрицательным сойтись не может никогда

From:

waxtep.livejournal.com

по-моему, можно так: представим "+1" как белый шарик, а "-1" - как черный. Неотрицательные числа представляем в виде соотв. кол-ва белых шариков (в т.ч. 0), а отрицательные - в виде фиксированного числа белых шариков, равного ceil(avg(x)) и соотв. числа черных шариков. Если в некоторой ячейке оказывается больше или равно белых шариков, чем черных, черные шарики "рекомбинируют" с белыми (из игры выбывают равные кол-ва черных и белых шариков). Каждый ход в игре сводится к перекладыванию черных и белых шариков, с обязательной рекомбинацией => кол-во черных шариков монотонно убывает => их в конце концов не останется.

From:

waxtep.livejournal.com

не, не работает, 1,-2,-1 => -1,2,-3 - как ни крути, а еще один черный шарик надо родить. хнык.

From: (Anonymous)

задача является частным случаем задачи физических колебаний с затуханием, поэтому интерес сразу пропадает

From:

Какой задачи с затуханием? Я вижу только, что можно ее так метафорически и неточно описать, а не что на самом деле частный случай.

From: (Anonymous)

Описание разумеется неточно. Общая физическая задача: 1) сохранение=фиксация центра колебания; 2) затухание=среднее (+2M) рассасывается по соседям (-M и -M).

Более элегантная и более общая формулировка задачи - для общего случая N и суммы 0. Случайно берутся позиции и перещелкиваются, две соседние сдвигаются в обратную сторону с сохраненим суммы. Доказать, что максимальная амплитуда стремится к нулю. Найти асимтотический закон.

From:

Чтобы доказать конечтность процедуры, достаточно найти норму, которая уменьшалась бы после каждого шага.
Обозначим через N_ij сумму чисел от N_i до N_j, с переходом по циклу, если j < i. Например

N₄₂ = N₄ + N₅ + N₁ + N₂.

Будем называть N_ij интервальными суммами пятерки N. В качестве нормы |N| пятерки N возьмем сумму модеулей интевальных сумм меньших нуля, то есть


|N| = foldr (+) 0 [ -N_ij | i <- [1..5], j<- [1..5], N_ij < 0 ].

Чтобы показать, что норма уменьшается, без ограничения общности можно предполагать, что применяется операция с использованием N₂, то есть, что N₂< 0 и новая пятерка имеет вид

N₁ + N₂ , -N₂, N₂+N₃, N₄,N₅.

Будем обозначать элементы этой пятерки через M_i, i=1,2,3,4,5, а саму пятерку через M.

Как будут выглядеть набор интервальных сумм для M?
Очевидно, что M_ij = N_ij, если ни i, ни j не равно ни одному из чисел 1,2,3, так как в этом случае соответствующие суммы либо вовсе не содержат N₁,N₂, N₃, либо содержат сумму

M₁ + M₂ + M₃ = N₁ + N₂ + N₃.

Пусть j &isin {4,5}. Тогда

M_1j = N_1j
M_2j = N_3j
M_3j = N_2j

M_j1 = N_j2
M_j2 = N_j1
M_j3 = N_j3

Остаются случаи, когда оба индекса принадлежат множеству 1,2,3:

где n сумма всех элементов в пятерке. Из этих вычеслений можно заметить, что чтобы превратить набор интревальных сумм для N в набор интервальных сумм для M, из него надо выбросить N₂₂ = N₂ и N₃₁ = n - N₂, а потом добавить M₂₂ = -N₂ и M₃₁ = n + N₂. Так как n положительно, а N₂ отрицательно, интервальная сумма N₃₁ положительна, а соответственно не учавствует в вычислении нормы пятерки N. Далее M₂₂ = -N₂ > 0, а значит не учавствует в вычислении нормы M. Теперь возможны два варианта:

если n+N₂ &ge 0, то |M| = |N| - abs(N₂) < |N|;

если n+N₂ < 0, то |M| = |N| - abs(N₂) + abs(n+N₂) = |N| + N₂ -n - N₂ = |N| -n < |N|.

From:

Я не проверял все выкладки, но разве вы пользуетесь где-то тем, что сумма исходных чисел положительна? Если это условие не выполняется, то утверждение неверно.

From:

Да, в последней строчке! (n означает сумму чисел в пятерке). Больше вроде нигде :)

From:

Еще немного выше, решая, что можно отбросить сумму n-N_2 :)

Здорово, да. Я пытался найти инвариант, и даже складывать последовательные цепочки членов и смотреть только на отрицательные среди них пытался, но я искал среди них "самую отрицательную" вместо того, чтобы сложить все вместе ;)

From:

Я забыл закончить доказательство. Надо добавить, что если |N| > 0, то существует i такое, что N_i < 0, а значит можно проделать операцию используя N_i. Так как норма на каждом шаге уменьшается, то рано или поздно мы получим N с |N| = 0. Но такое N обязано состоять лишь из неотрицательных чисел, так как если N_i < 0 для некоторого i, то |N| &ge -N_i > 0.

From:

Да, вроде все верно. Красиво, поздравляю! надеюсь вам понравилось с ней возиться :) мое решение, которое сейчас как раз дописал, раза в три длиннее и далеко не так элегантно. Сейчас пошлю его отдельным комментарием.

From:

Кстати, мне указали на то, что в вашем доказательстве достаточно рассматривать суммы вида S_ii, S_i+2_i, т.е. числа вида N_i, S-N_i, а все остальные выкинуть.

From:

Мое решение (по-английски, очень длинно и неэлегантно; есть решение куда проще в комментариях выше):

Let's call the rules as stated a positive-sum positive-direction game (because we change -x -> +x in the positive direction). We can also consider variants with negative initial sum and/or negative direction, where +x -> -x and the neighbors get a positive boost. Finally we'll need to look at a variant with no wraparound - that is, when inverting an edge
number only one neighbor gets a boost, changing the total sum.

Given any variant of the rules and an initial tuple, there are three
conceivable outcomes: the game "diverges", producing unbounded
numbers; the game stops, because all the numbers are nonnegative (or
nonpositive for a neg-direction game); the game goes into a cycle
repeating the same bounded set of tuples. I'll prove that for a
pos-direction game with wraparound, regardless of the initial tuple
and choices of numbers to invert, the outcomes are as follows,
depending on the total sum:

positive sum -> the game stops (this solves the puzzle as requested)
negative sum -> the game diverges
zero sum -> the game goes into a cycle.

Note that it's easy to flip both the sign of the sum and the direction
of play by inverting the signs of all numbers, obtaining essentially
the same game; so the above claim also solves the neg-direction case
with the condition on the sum inverted.

I first need a lemma to show what happens in a no-wraparound game with
few numbers:

Lemma 1. A no-wraparound positive-direction game with 2 or 3 numbers
will stop at a nonnegative tuple in a number of steps that depends
only on the initial sum, not the numbers themselves.

Proof: With two numbers, after one step one of them will be positive,
e.g. [-A B], then after the next step we get [A B-A], and if B-A is
negative, this transforms into [B A-B] with both numbers nonnegative,
so we're done after at most 3 steps.

With three numbers A B C, every time we invert an edge number, we
increase the total sum at least by 1 (due to no-wraparound), and we do
that at least every second step, because we can't invert B twice in a
row. So after a number of steps depending only on the initial sum, the
total sum becomes nonnegative. After that, I'll show that all numbers
become nonnegative in at most 4 steps. If two numbers are negative,
e.g. -A -B C, then C >= A+B by sum being nonnegative, so inverting A
or B leaves just one negative number. So assume just one number is
negative, and there are two cases of it being on the edge or in the
middle:

[-A B C] -> [A (B-A) C]. Now if B-A is negative, this -> [B (A-B)
(C+B-A)], and C+B-A >=0 being the initial sum, so we're done.

[A -B C] -> [(A-B) B (C-B)]. Suppose e.g. A-B is negative and inverted
-> [(B-A) A (C-B)],if
C-B is also negative, then this -> [(B-A) (A-B+C) (B-C)], and this is
nonnegative, the middle
number being the initial sum. Q.E.D.

Now we go back to 5 numbers with wraparound. An easy consequence of
the above lemma is:

Lemma 2, the "hanging gun" lemma: If A,B are two neighbors, A+B < 0,
in a tuple in a positive-direction game, the game will produce a
number <= A+B in a number of steps dependent only on the total sum. A
and B are like a gun hanging on the wall in act 1 that must eventually
fire by the end of the play.

Proof: If either A or B are inverted, the other number becomes A+B. As
long as they're not inverted, they can only decrease due to their
other neighbors being inverted. Avoiding A and B and using only three
other numbers amounts to a game with 3 numbers and no wraparound,
which by Lemma 1 must end in K steps, where K depends on the sum of
the three numbers; this sum is bounded from below by the total sum
because A+B < 0. Q.E.D.

From:

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.

From:

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].

From: (Anonymous)

Как изменится результат, если убрать условие целочисленности?

From:

Думаю, что никак. Решение vanya_y выше, похоже, сразу подходит для действительных чисел.

From: (Anonymous)

М-м-м... Если я правильно понял, там используется следующий аргумент: норма на каждом шаге уменьшается, ввиду целочисленности она уменьшается минимум на 1, поэтому за конечное число шагов она достигнет нуля. Неясно, откуда для вещественных чисел (например, несоизмеримых) следует, что «шаг» умешьшения нормы всегда будет отделён от нуля положительной константой.

From:

drhoenikker.livejournal.com

Isn't it enough to use as the norm the sum of absolute values plus 0.1*number of negative numbers?

From: