Stephen E. Wilson: The Ring of Fire: solved by rocks and fishes

Datum objave: 17. 4. 2015
Seminar za diskretno matematiko
Torek, 21. 4. 2015, od 10h do 12h, Plemljev seminar, Jadranska 19
Povzetek. The Ring of Fire is a problem that baffled me for 25 years. Here it is: You are given a circle of five integers; some positive, some negative, and the sum of all of them is positive. As long as there is at least one negative number in the ring, select one and then 'pop' it by replacing it with its absolute value and then adding the negative version to both of its neighbours. In symbols, replace  b  -c  d  with  b-c  c  d-c. Notice that this leaves the sum unaffected.  For instance we could have
-1  6  2  -5  1
Popping the -5 gives
-1  6  -3  5  -4
Then popping the -4 gives
-5  6  -3  1  4.
You are to give an elementary proof that this process eventually terminates, i.e., that no matter what sequence of negatives you choose to pop, eventually all of the numbers on the circle will become non-negative.  We use   rocks   and   fishes   to describe the situation.  And we propose a further unsolved problem for which rocks and fishes provide no help.