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

[avva]

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

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

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

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

Comments

[roma.livejournal.com]

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.

[roma.livejournal.com]

PS I meant the "Affine A2" picture.

[avva.livejournal.com]

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?

[roma.livejournal.com]

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.

[vanja-y.livejournal.com]

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

[roma.livejournal.com]

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.