Communications of the ACM
Last byte
Puzzled: Solutions and Sources
Solution: To prove that the opinions eventually become fixed or cycle every other day, think of each acquaintanceship between citizens as a pair of arrows, one in each direction. Let us say an arrow is currently "bad" if the party of the citizen at its tail differs from the next-day's party of the citizen at its head.
Consider the arrows pointing out from citizen Clyde on day t, during which (say) Clyde is a Democrat. Suppose that m of these arrows are bad. If Clyde is still (or is again) a Democrat on day t+1, then the number n of bad arrows pointing toward Clyde at day t will be exactly m.
If, however, Clyde is a Republican on day t+1, n will be strictly less than m since it must have been that the majority of his friends were Republican on day t. Therefore a majority of the arrows out of Clyde were bad on day t-1, and now only a minority of the arrows into Clyde on day t are bad.
The same observations hold if Clyde is a Republican on day t-1.
But, here's the key: Every arrow is out of someone on day t-1 and into someone on day t. Thus, the total number of bad arrows cannot increase between days t-1 and t; in fact, that number will go down unless every citizen had the same opinion on day t-1 as on day t+1.
But the total number of bad arrows on a given day cannot decrease forever and must eventually reach some number k from which it never descends. At that point, every citizen will either stick with his or her party forever or flop back and forth every day.
The puzzle can be generalized considerably by, for example, adding weights to vertices (meaning some citizens' party memberships are more prized than others), allowing loops (citizens who consider their own current opinions as well), and allowing tie-breaking mechanisms and even different thresholds for party changes.
Source: This puzzle was suggested to me by Sasha Razborov of the Institute for Advanced Study in Princeton, NJ, who says it was considered for an International Mathematics Olympiad but rejected as too difficult. It was posed and solved in a paper by Goles, E. and Olivos, J. Periodic behavior of generalized threshold functions. Discrete Mathematics 30 (1980), 187189.
2. Island of Foosgangland
Solution: Suppose there are n intersections and m paths in Foosgangland; we may assume the paths are numbered 1 through m. Since each path has two ends, the average number of paths meeting at an intersection is 2m/n.
Let us place a pedestrian at every intersection. At time 1, the pedestrians at each end of path 1 change places, giving a friendly wave as they pass each other in the middle of the path. At time 2, the pedestrians currently at each end of path 2 change places. This continues until at time m, the pedestrians who find themselves at each end of path m change places.
What has happened here? Observe first that every one of the n pedestrians has taken an "increasing walk"; that is, he or she has walked a path, rested, then walked a higher-numbered path, and so forth. Since every edge has been traversed twice, the total length of all these walks is 2m. But then the average length of the walks is 2m/n, and it follows that at least one of the paths has length at least 2m/n, and we are done.
Source: This puzzle and its elegant solution were passed to me by Ehud Friedgut of The Hebrew University of Jerusalem. We traced the puzzle back to the fourth problem in the second round of the 1994 Bundeswettbewerb Mathematik, one of two major German mathematical competitions.
3. Graph Coloring Game
This puzzle remains unsolved as of this writing. We have no idea how to go about it. The usual approaches (such as symmetrization, strategy stealing, and induction) don't seem to work. But surely it should be true, don't you think?
©2008 ACM 0001-0782/08/0900 $5.00
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. To copy otherwise, to republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee.
The Digital Library is published by the Association for Computing Machinery. Copyright © 2008 ACM, Inc.
No entries found