last byte
DOI: 10.1145/2184319.2184346
Peter Winkler
Puzzled
solutions and sources
Last month (May 2012) we posted a trio of brainteasers concerning designs
on square grids. Here, we offer solutions to all three. How did you do?
1.Tiling a 4× 4 Grid. Solution. You were given 16 unit
squares, each containing a different
combination of vertical crossing line,
horizontal crossing line, SW-NE diagonal, and SE-NW diagonal. Your object
was to tile a 4×
4 grid with these squares
in such a way that no line ends before it
hits the edge of the grid—or prove it cannot be done. Figure 1 shows a solution,
though there are several; it is indeed
possible to arrive at one without much
trial and effort, by, say, reasoning about
how the long diagonal lines should be
arranged. Note that if you identify the
left and right boundaries of the square
grid to form a cylinder, the lines continue to match up. Moreover, if you identify
the top and bottom boundaries as well,
so you now have a doughnut, or torus,
all the lines will be endless loops. The
puzzle’s composer, Barry Cipra, noted
the curious fact that all solutions work
on the torus; see http://www.funmath-
club.com/students/sollewitt.html. It is
not surprising that the horizontal and
vertical lines match up on the torus.
They have to. But why do the diagonals
happen to match up as well?
2.Circles on a Torus. Solution. In a second version of
Puzzle 1, each unit square contained
one of the 16 possible combinations
of four quarter-circles, each of radius
1/2 and centered at a corner. You were
asked to tile a 4×
4 grid with these
squares so no path ends before it hits
the edge of the grid or, better, so an
even number of quarter-circles meet
at each edge shared by two squares.
Figure 2 shows a solution satisfying
both conditions, with the additional
property that the curves form a collection of circles and semicircles. But
you can do better. See if you can find
a solution that matches left-right and
top-bottom edges so you get nothing
but circles on a torus.
figure 2.
the grid, with each diagonal using two
of them, so you certainly cannot get
more than 18 diagonals in the grid.
Moreover, along each side of the grid
are six vertices and only five squares,
so, on each side, some vertex will go
without a diagonal. If three or more
vertices are left without diagonals,
the maximum number of diagonals is
16. The only way the four sides can be
handled with fewer than three empty
vertices is if two are at opposite corners of the grid (at, say, the S W and NE
corners) with no other empty vertices
along the grid. But then every square
touching a side of the grid would have
to contain a SE-NW diagonal—an impossibility, because diagonals would
then meet at the vertices diagonally
opposite the empty grid corners.
figure 3.
figure 1.
3.Diagonals in a 5× 5 Grid. Solution. You were asked to
place as many diagonals as you can
into a 5×
5 grid with no two meeting at a corner (or crossing inside
a square); Figure 3 shows you can
achieve 16 diagonals. To see that
more are impossible, note first that
there were only 6×
6 = 36 vertices in
All readers are encouraged to submit prospective
puzzles for future columns to puzzled@cacm.acm.org.
Peter Winkler ( puzzled@cacm.acm.org) is William Morrill
Professor of Mathematics and Computer science, at
dartmouth College, Hanover, nH.
© 2012 aCM 0001-0782/12/06 $10.00