Five integers with positive sum are assigned to the vertices of a pentagon. At any point you may select a negative entry (say, -x) and flip it to make it positive, or x, but then you must subtract x from each of the two neighboring values; thus, the sum of the five integers remains the same. For example, if the numbers are 2, 4, -3, 1, -3 [in that order on the pentagon's vertices], you can either flip the first -3 to get 2, 1, 3, -2, -3 or the second to get -1, 4, -3, -2, 3. Now prove that no matter what numbers you start with and strategy you follow, all the numbers will eventually become non-negative, and thus the procedure terminates after finitely many steps.Now, be honest and don't go all over the internet looking for the solution. I have the solution in the magazine, but I haven't looked at it, and will be trying to solve it myself :-) But it's good to know that I have the solution somewhere and have a standard to compare against. Now show your mathematical might! :-)
Wednesday, March 18, 2009
A Termination Puzzle
Here is an interesting puzzle I saw in the print version Communications of the ACM. See if you can solve it and let me know of your solution in the comments:
Subscribe to:
Post Comments (Atom)
3 comments:
This is going to be my very informal intuition behind the solution:
WLOG, assume the vertex b is negative, and that vertex a is adjacent to vertex b. We are going to flip the sign of vertex b. Now, from the point of view of a, there are 3 cases:
1. a == b. Then when we flip, both vertices are not negative, thus we decrease the number of negative vertices by one.
2. a > b. Then when we flip, both vertices are not negative, thus we decrease the number of negative vertices by one.
3. a < b. This is the interesting case, by flipping b we decrease the number of negative vertices, but we possibly increase the number of negative vertices with a-b. WLOG assume a was positive (since the sum of vertices was positive there must be some positive vertices). Now we know that the new a (a-b) is negative, so we can flip a. We also know that a < b. Thus, when we flip a, b will remain positive because of case 2, thus reducing the number of negative vertices.
Arg those should be
1. a == |b|
2. a > |b|
3. a < |b|
of course :-p
@Scott I was starting to feel a little suspicious of your thinking processes until I saw the second comment :-P Yeah, this looks like what I had in mind, though I suspect the actual proof is a bit more involved and might include more cases (I haven't looked at the solution yet... I will post it in a comment later on).
Post a Comment