last byte
DOI: 10.1145/1378704.1378726
Peter Winkler
Puzzled
Delightful Graph theory
Welcome to the new puzzle column. Each column will present three puzzles. The first two will have known
(and usually elegant) solutions that will appear in the next issue of Communications. The third will be an
open problem; good luck with that one.
Readers are encouraged to submit prospective puzzles for future columns to puzzled@cacm.org.
We start with three delightful graph-theoretic puzzles. Here we go.
1.Si nce this is an
election year, it seems
appropriate to visit that
impressionable town in
which, every evening,
each citizen calls all his
(or her) friends (always
an odd number) and
re-chooses his party
affiliation—Republican
or Democrat—the next
day, in accordance with
the majority of his friends
at the time of the call.
Can you show that, after
a while, party affiliations
will be the same on every
alternate day?
2.Th e island of
Foosgangland
boasts a complex web
of footpaths. Each
section of path, from
one intersection to the
next, is identified by a
different number. If you
happen to take a walk
in Foosgangland, the
“length” of your walk is the
number of path sections
you traverse, and your walk
is “increasing” if the path
numbers you encounter
are always go up. Prove
that there is someplace
on the island where you
can take an increasing
walk whose length is
at least the average
number of paths meeting
at the intersections in
Foosgangland.
3.In a graph-coloring
game, a finite graph
G and a palette of k colors
are fixed. Alice and Bob
alternately choose an
uncolored vertex of G and
color it with a color not
previously used on any
neighboring vertex. Alice,
who goes first, wins if all
the vertices get colored;
but if anyone gets stuck
before that happens,
Bob wins. (The game is
described in an article—
Bartnicki, T., Grytczuk, J.,
Kierstead, H.A., and Zhu,
X. The map-coloring game.
American Mathematical
Monthly 114, 9 (Nov. 2007),
793–803—that pointed out
that the following question
remains embarrassingly
open: Are there a G and a k
such that Alice wins on G
with k colors, but Bob wins
with k+ 1?)
Peter Winkler ( puzzled@cacm.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.