Hosted by The Math Forum

Problem of the Week 1149

Doughnut King

_____________________________________________
MacPoW Home ||  Forum PoWs ||  Teachers' Place ||  Student Center ||  Search MacPoW
_____________________________________________

The graph of king's moves on a 4×3 chessboard uses vertices to represent squares and edges for all legal king moves. There are 12 vertices, which look like this:

The problem: Color the edges of the king graph on a torus using 8 colors, so that edges that meet at a vertex get different colors.

On a torus the king (just like Mr. or Ms. Pac-Man) can leave the right edge and enter on the left, or exit the top and enter on the bottom. The diagram at left below duplicates 2, 3, 4, 5, 9 and quadruplicates 1 to show all the edges. Each of the 12 vertices has 8 neighbors, so you have 12 × 8/2 = 48 edges to color. The torus at right shows what the 3-dimensional board really looks like: the big dots are the centers of the squares.

© Copyright 2011 Stan Wagon. Reproduced with permission.

[Privacy Policy] [Terms of Use]

_____________________________________
Home || The Math Library || Quick Reference || Search || Help 
_____________________________________

© 1994-2014 Drexel University. All rights reserved.
http://mathforum.org/
The Math Forum is a research and educational enterprise of the Drexel University School of Education.The Math Forum is a research and educational enterprise of the Drexel University School of Education.


23 November 2011