1. election Year
solutions and sources
Last month (August 2008, p. 104) Peter Winkler posed a trio of brain teasers
in his “Puzzled” column. Here, he offers some solutions. How well did you do?
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
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), 187–189.
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
Peter Winkler ( firstname.lastname@example.org) is Professor of
Mathematics and of Computer Science and Albert Bradley
Third Century Professor in the Sciences at Dartmouth
College, Hanover, NH. He has written two puzzle books:
Mathematical Puzzles: A Connoisseur’s Collection and
Mathematical Mind-benders, both published by A K Peters,
Ltd., Wellesley, MA.