Communications - June 2012

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