«Contents Ü Foreword Elwyn Berlekamp and Tom Rodgers ½ I Personal Magic ¿ Martin Gardner: A “Documentary” Dana Richards ½¿ Ambrose, Gardner, ...»
We are now ready to prove the theorem. We shall argue by contradiction, supposing that Ñ´Äµ ½. The contradiction will be to show that under this assumption É has a winning strategy. The basic idea resembles Nash’s proof that the ﬁrst player has a winning strategy for Hex, in that we will describe a new strategy for É in which (in effect) É makes an extra move and then plays the reﬂected version ÄÊ of È ’s hypothetical winning strategy Ä. (Note that Ñ´Äµ Ñ´Ä Ê µ.) The proof is complicated, however, by the fact that it is not clear a priori that having an extra stone on the board is either an advantage or a disadvantage. The proof splits into two cases depending on whether É is the ﬁrst player or the second.
Suppose that É is the ﬁrst player. Player É applies the following strategy. She makes an arbitrary ﬁrst move, and draws a circle around the cell containing this move. From now on she applies strategy Ä Ê in what we shall call the imaginary game. The state of this game is exactly like that of the real game, except that in the imaginary game the encircled cell is empty, while in the real game, that cell contains a É-stone. This relationship will be maintained throughout the game. When the strategy Ä Ê requires É to play in the encircled cell, she plays instead into another empty cell (chosen arbitrarily), erases the circle, and draws a new circle around the move just played. Because Ñ´ÄÊ µ ½, when it is È ’s turn to move there must be at least two empty cells in the imaginary game, and there must be at least one empty cell in the real game. Therefore it is possible for È to move. (We’ll see below that È will not have won the real game.) Similarly, when it is É’s turn to move there must be at least three empty cells in the imaginary game, so there are at least two empty cells in the real game. Thus the real game can continue.
Eventually É will win the imaginary game because Ä Ê is a winning strategy. When this happens she has also won the real game, because of the monotonicity property. This contradicts our assumption that È has a winning strategy.
Now, suppose that É is the second player. Let Ô ¼ be È ’s ﬁrst move.
Player É begins by encircling Ô¼, playing out ÄÊ in an imaginary game.
240 J. LAGARIAS AND D. SLEATOR The imaginary game and the real game differ in up to two places, as follows. The imaginary game is obtained from the real game by ﬁrst changing Ô¼ from È ’s stone to É’s stone, then by erasing the stone in the encircled cell. If the strategy ÄÊ requires a move into the encircled cell, then É arbitrarily chooses a different empty cell in which to move, and transfers the circle from its current location to the new cell. The fact that Ñ´Ä Ê µ ½ ensures that both players can continue to move. It is easy to see that the relationship between the real game and the imaginary game is maintained.
Player É eventually wins the imaginary game. The position in the real game is obtained from the position in the imaginary game by putting É’s stone in the encircled cell, and changing the contents of Ô¼ from a É-stone to a È -stone. The position in the imaginary game is a winning position for É, and the monotonicity property ensures that the corresponding position in the real game is also a win for É. This contradicts our assumption that È has a winning strategy.
References  A. Beck, M. Bleicher, and J. Crow, Excursions into Mathematics, Worth, New York, 1969, pp. 327–339.
 R. Evans, A winning Opening in Reverse Hex, J. Recreational Mathematics, 7(3), Summer 1974, pp 189–192.
 D. Gale, The Game of Hex and the Brouwer Fixed-Point Theorem, The American Mathematical Monthly, 86 (10), 1979, pp. 818–827.
 M. Gardner, The Scientiﬁc American Book of Mathematical Puzzles and Diversions, Simon and Schuster, New York, 1959, pp. 73–83.
 Y. Yamasaki, Theory of Division Games, Publ. Res. Inst. Math. Sci., Kyoto Univ.
14, 1978, pp. 337–358.
An Update on Odd Neighbors and Odd Neighborhoods Leslie E. Shader
Some time ago (1986–88) this problem appeared in mathematical circles:
Problem 1: Can the unit squares of an Ò ¢Ò sheet of graph paper be labeled with 0’s and 1’s so that every neighborhood is odd?
A neighborhood, Æ, of square, is the set of squares sharing an edge with square and does include square. A neighborhood, Æ is odd if there are an odd number of squares in Æ with labels “1".
Figure 1 shows a 4 ¢ 4 example with a desired labeling.
But is symmetric, so Ý Ý Ì ¼. Therefore, ÝÝÌ ¼ and rank´ · Áµ rank ´ · Á ½µ, so ´ · ÁµÜ ½ for every adjacency matrix. Finally, for every graph, the vertices of can be labeled with 0’s and 1’s so that every neighborhood in is odd.
If we think of the unit squares in Problem 1 as vertices of and Ú Ú is ´µ Ú shares an edge with Ú, then Theorem 1 implies that an edge in the squares of the Ò ¢ Ò square can be labeled with 0’s and 1’s so that each neighborhood is odd.
Now for some new questions (at least at the time that this paper was submitted).
The Developer’s Dilemma Suppose a real estate developer has an inﬁnite (at least sufﬁciently long) strip of land Ñ lots wide.
Further, we assume all lots in the ﬁrst strip of Ñ lots have been sold. It is quite possible that some of the buyers are odd, and some are not odd. Is there an Ò so that the developer can sell all the lots in the Ñ ¢ Ò rectangle and satisfy the politically correct criteria that all neighborhoods have an odd number of odd neighbors?
When this paper was originally written, the answer to the Developer’s Dilemma was unknown. We will generalize, as before, to all graphs and prove a theorem. But this time the generalization does not yield a solution to the Developer’s Dilemma. However, a proof that the Dilemma can be solved will also be presented.
Theorem 2. Let be a graph with vertices labeled with 0’s and 1’s in any way.
If not all neighborhoods of are odd, then can be embedded in a graph ¼, with all neighborhoods in ¼ odd.
ODD NEIGHBORS AND ODD NEIGHBORHOODS 243It is rather interesting that only one vertex must be added to in order to prove Theorem 2.
since the sum counts the edges from vertices labeled 1 exactly twice. Hence, there are an even number of vertices ¾ labeled 1 and Æ is even in.
These vertices now are all connected to Û with label 1. So Æ Û is odd ¾ ¼.
Theorem 3. The Developer’s Dilemma can be solved.
Proof. Let the Ñ ¢ ½ strip of unit squares be horizontal. We call Ú ½, any 0–1 Ñ-tuple, a “starter" for the Ñ ¢ Ò rectangle we seek. We wish to construct a proper labeling of an Ñ ¢ Ò rectangle so that all neighborhoods are odd and the vector Ú½ is the “starter" column.
Perhaps the Ñ ¢ ½ rectangle using the starter Ú ½ has the property that all neighborhoods are odd. Figure 3 shows that this phenomenon can happen.
· is odd, let Ü½ ¼, otherwise Ü½ ½.
If · · is odd, let Ü¾ ¼, otherwise Ü¾ ½.
If · · is odd, let Ü¿ ¼, otherwise Ü¿ ½.
If · · is odd, let Ü ¼, otherwise Ü ½.
If · is odd, let Ü ¼, otherwise Ü ½.
If Of course, Ñ is not limited to the value 5. Now that every neighborhood for Ú½ is odd, we can repeat the process for column 2. Each neighborhood will now have all but one entry labeled, and that label can be assigned so that the neighborhood is odd.
This process can be repeated as many times as we like, and each new column will be dependent on just the preceding two. We will have a solution to our problem if the Ò · ½ column has all entries 0, i.e., Æ Ò is odd for square Ú in column Ò Ò. Since there are only a ﬁnite number of adjacent pairs of the Ñ-tuple, either we get a column of 0’s or there must be an adjacent pair that repeats in our process. Let Ú Ú ·½ be the ﬁrst pair that repeats. We can generate new columns moving from left to right or from right to left, and we generate a second Ú Ú ·½ somewhere to the right of the ﬁrst Ú Ú ·½ (see Figure 4).
Ú½ ¡ ¡ ¡Ú Ú ·½ ¡ ¡ ¡Ú Ú ·½
Using the second occurrence of Ú Ú ·½, column Ú ½ must repeat to the left of the ﬁrst occurrence of Ú Ú ·½.
Ú½ ¡ ¡ ¡Ú ½Ú Ú ·½ ¡ ¡ ¡Ú ½ Ú Ú ·½So Ú Ú ·½ is not the ﬁrst repeating pair. Contradiction! Hence there is a column of 0’s and the proof is complete.
Figure 5 shows an example where Ú ½ col´¼¼½½¼µ, and Ò.
The Problem It is well known that a ray of light can reﬂect many times between two ordinary line mirrors. If we introduce the condition that a ray should reﬂect only one point on the mirror — reducing the mirrors to point mirrors — we ﬁnd a maximum of three reﬂections for two mirrors and seven reﬂections for three mirrors, if these are suitably placed and oriented. Solutions are shown in Figure 1.
Figure 1. Maximum number of reﬂections for two and three point mirrors (E = entrance mirror, P = perpendicularly reﬂecting mirror).
This suggests an intriguing problem: How must Æ point mirrors be placed and oriented to reﬂect an entering ray of light as often as possible between these mirrors? What is the maximum number of reﬂections for varying Æ?
Upper Limits. From Figure 1 we can see that after some reﬂections the ray of light is reﬂected perpendicularly onto a mirror P and returns along the same paths but in the opposite direction. If the ray would not return along the entry paths, passing once again by entrance mirror E, half of the potential reﬂections would not be used. It is obvious that the strategy of 246 M. O. VAN DEVENTER
Figure 2. Number of reﬂections for different mirror types.
using a perpendicularly reﬂecting mirror P yields the maximum number of reﬂections.
At each mirror a maximum of Æ ½ rays can be reﬂected, going to every other mirror. At mirror E there can be one additional reﬂection for the entering ray. Therefore, the theoretical maximum number of reﬂections is Æ´Æ ½µ · ½, or Æ¾ Æ · ½ Ê½ ´½ µ However, for even Æ there is a parity complication. Only at mirror P can there be an odd number of reﬂections. At all other mirrors there must be an even number of reﬂections, since the light paths are used in two directions;
see Figure 2.
At mirror E there can be at most Æ reﬂections, Æ ½ from the other mirrors and one from the entering ray. At mirror P there can be at most Æ ½ reﬂections, from the other mirrors, which is an odd number. However, at the other Æ ¾ mirrors (other than the E and P mirrors) there can’t be Æ ½ reﬂections, but only Æ ¾ to make it an even number. So the upper limit for an even number of mirrors is Æ · ´Æ ½µ · ´Æ ¾µ´Æ ¾µ or Æ ¾ ¾Æ · ¿ Ê¾ ´½ µ For odd Æ the parities are okay if E and P are the same mirror, so Ê½ remains valid.
Mirrors on the Corners of a Regular Polygon Can the theoretical maxima Ê ½ and Ê¾ be achieved for any Æ, and what should the positions and the orientations of the mirrors be? A well-known geometrical property may help us: When the Æ mirrors are put on the corners of a regular Æ-gon, the angle between all the neighboring pairs of light paths is 180 Æ Æ, as shown for the regular pentagon in Figure 3.
POINT MIRROR REFLECTION 247
Figure 3. Light paths in a regular pentagon.
Using such an Æ-gon grid, two-dimensional space is sufﬁcient to ﬁnd solutions for each Æ. Only discrete orientations of the mirror are allowed and are multiples of 90 Æ Æ, say Ñ ¢ ¼Æ Æ. For Ñ ¼ we have the normal orientation, Ñ ½ yields a rotation of one step clockwise, and so on. This is illustrated in Figure 4.
Figure 4. Rotation of a mirror.
Prime Number of Mirrors. For prime Æ the maximum number of reﬂections can always be achieved. We take Ñ ½ for E (= P) and Ñ ¼ for all other mirrors. The ray of light, starting at mirror E, makes hops of one mirror; after passing mirror E again, it makes hops of two mirrors, and so on. Since Æ is prime, the ray will pass every mirror once at each tour from E to E; see Figure 5.
Non-Prime Number of Mirrors. If the number of mirrors is non-prime, the investigation of various cases is less straightforward. A systematical trialand-error search for the maximum number of reﬂections may be performed
using the following strategy:
Step 1. Draw the Æ-gon and all possible light paths (the Æ-gon grid).
Add the starting ray at an angle of ½ ¼ Æ Æ with the Æ-gon.
Step 2. Omit one or more light paths (lines of the Æ-gon grid), and adjust the mirror orientations such that symmetry of light paths is preserved at every mirror and such that only at mirror P is there a perpendicular reﬂection.
Prevent any obvious loops, since a ray can neither enter nor leave such a loop.
248 M. O. VAN DEVENTER
Figure 5. Reﬂection diagrams for prime numbers of mirrors.
Step 3. Count the number of reﬂections by following the entering ray.
Calculate whether the number of reﬂections is equal to two times the number of remaining light paths plus one. If this is true, there are no loops and all of the remaining light paths are used. If not, reject the candidate solution.
Repeat Steps 2 and 3 for all candidates missing one light path, then for all candidates missing two light paths, and so on, until one or more solutions are found.
Figure 6 illustrates the procedure for the case of six mirrors. At least two light paths have to be omitted for Step 2. The candidate has 13 light paths.