Communications of the ACM
Last byte
Puzzled: Solutions and Sources
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.
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 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 SW 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.
Footnotes
All readers are encouraged to submit prospective puzzles for future columns to [email protected].
©2012 ACM 0001-0782/12/0600 $10.00
Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and full citation on the first page. Copyright for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, to republish, to post on servers, or to redistribute to lists, requires prior specific permission and/or fee. Request permission to publish from [email protected] or fax (212) 869-0481.
The Digital Library is published by the Association for Computing Machinery. Copyright © 2012 ACM, Inc.
No entries found