Info

3. 17, 50, 25, 74, 37, 110, 55, 164, 82, 41, 122, 61, 182, 91, 272, 136, 68, 34, 17,____

Michael Beeler, William Gosper and Rich Schroeppel give these results in HAKMEM (short for "Hacker's Memo"), Memo 239, Artificial Intelligence Laboratory, M.I.T., 1972, page 64. No one has yet come up with good ideas about how to establish the general case for all nonzero integers. (Zero, of course, is already in a 0, 0, 0, . . . loop.) No one knows if there are other loops, or if there are integers that generate a nonlooping series of numbers that diverge to infinity.

Gosper and Schroeppel, incidentally, proved an amusing loop conjecture involving English names for numbers (HAKMEM, page 64). Spell out the name of any number. It need not be rational or even real. Counting numbers must be named directly, and not by such circumlocutions as "twelve plus one" or "twenty minus five," and so on. Replace the name by the number of digits in the name and keep repeating the procedure. Example: the cube root of pi, fifteen, seven, five, four, four, four, The series always, and quickly loops at four.

In explaining a recent triangle-dissection problem, Ogilvy wrote that it might "have a solution before this book appears." He was right. It had been known that any triangle can be cut into four triangles similar to itself, or into n triangles similar to itself when n is 6 or more. If n is 2 or 3, only a right triangle can be properly cut. If n is 5, a right triangle can be dissected into five triangles similar to itself, but for nonright triangles the conditions for dissection were unknown when R. W. Freese, Ann K. Miller and Zalman Usiskin wrote their article "Can Every Triangle be Divided into n Triangles Similar to It?" (The American Mathematical Monthly, Volume 77, October, 1970, pages 867-869).

Recently it has been independently proved by several people that when n is 5 and the triangle has no right angle, it can be cut into five triangles similar to itself if and only if one angle is 120 degrees and the others are each 30 degrees [see Figure 120]. This unique dissection is given in "Partitioning a Trian-

A unique dissection

gle into 5 Triangles Similar to It" (Mathematics Magazine, Volume 45, January, 1972, pages 37-42), by Z. Usiskin and S. G. Wayment. Still open are questions such as: Which triangles can be cut into n similar triangles not similar to themselves? For what values of n can a quadrilateral be cut into n quadrilaterals similar to one another and/or to itself?

In 1960, Stanislaw M. Ulam, another virtuoso puzzle maker, published a fine collection of advanced unsolved problems, most of them original. The book was reprinted in 1964 as a paperback, Problems in Modern Mathematics. One of Ulam's topological-game problems seemed as uncrackable as it was curious. Imagine a cube divided into a lattice of unit cubes, like a three-dimensional checkerboard. Players take turns marking a unit edge of the lattice. The first player marks any edge. Thereafter each marked edge must join the previously marked edge. One end of the path remains fixed as the other end grows one unit in length with each move, as though a bug were crawling along the lattice lines and leaving a trail. Since the lattice is finite, the path must eventually intersect itself to form a closed-space curve. One of the players wins if the curve is knotted. The other player wins if there is no knot. Who wins when the game is played rationally?

John Horton Conway, a University of Cambridge mathematician, found an ingenious proof that the "no knot" player can always win regardless of whether he goes first or second. Assume that the game is played on a three-by-three-by-three cube (a lattice of 27 unit cubes). This is the smallest cube on which the path can knot. The following no-knot strategy extends readily to all cubes of higher orders.

Through each lattice point there are various planes that are perpendicular to a body diagonal (a diagonal joining diametrically opposite corners) of the large cube. We shall call such a plane a primary plane, or P plane. If the P plane goes through a corner of the large cube, there may be only one adjacent plane parallel to it and passing through points adjacent to points on the P plane; otherwise there will be two such adjacent planes, one on each side of the P plane. We call these A planes.

Imagine all lattice points on A planes—call them A points— projected on the P plane, together with all edges joining A points to P points. This puts on the P plane a graph equivalent to one of the five shown in Figure 121. On each graph black vertexes are lattice points originally on the P plane. The open circle vertexes are A points projected from A planes. The C's mark the corners of the large cube.

Figure 121

Graphs for Stanislaw M. Ulam's knot game

Note that the three graphs on the left have loose ends. Those on the right do not. Conway has shown (his unpublished proof is not difficult) that, given any lattice point, one can always find passing through it a P plane on which the graph has no loose ends.

If your opponent goes first, you should choose a P plane through either end of the marked edge that has a no-loose-ends graph. One end of the path will be on an A plane. Play so that the path returns to the P plane, that is, join the colored end of the path to a black vertex. Each succeeding move by your opponent must take the path off the P plane (to a colored spot). Your strategy is always to return the path to the P plane by extending it to a black spot. Because the graph has no loose ends, and because its colored and uncolored vertexes alternate, you can always do so. It is obvious that when the path first closes, it will have to be unknotted.

If you go first, mark any edge. After your opponent has moved choose a P plane that goes through the path's middle vertex and on which the graph has no loose ends. Your no-knot strategy is the same as before. Play so that the path always returns to the P plane; in other words, always extend the path to a black vertex. The path cannot be knotted when it first intersects itself.

"I think it was obvious from the start," Conway writes in a letter, "that the no-knot player had the best of it. He only had to make the path close, whereas the other player really had to do things."

Conway's strategy does not apply to noncubical "brick" lattices (because finding a no-loose-ends graph is not always possible) or to cubical games in which the no-knot player goes first and moves are allowed at all times at either end of the growing path. In both cases, so far as I know, winning strategies remain unknown.

Three-dimensional lattices are awkward "boards" for actual play, but closely related topological games on planar lattices make excellent pencil-and-paper contests. David L. Silverman, whose book Your Move includes several such games, is responsible for the latest fad among Los Angeles puzzlers: an unpublished, unsolved game that Silverman calls Slither. Its five-by-six-point lattice is just large enough to have resisted all efforts to determine which player has the win [see Figure 122]. In a tab-

Figure 122

The game of Slither ulation of several hundred games the wins were about equally divided between first and second players. The rules are simple. Opponents take turns marking an orthogonal unit segment. The segments must form a continuous path but may be added to either end of the preceding path. The player forced to close the path is the loser. (If the first to close it wins, it is a duller game, although even that version is unsolved.) The illustration shows a typical position in which the next play must be a losing one. Perhaps a reader will discover a winning strategy for either version (or both versions) of Slither.

Hallard T. Croft, a colleague of Conway's at Cambridge, periodically sends lists of new unsolved problems to his friends. A few years ago one of Croft's problems asked if there existed a finite set of points on the plane such that the perpendicular bisector of the line segment joining any two points would always pass through at least two other points of the set. The problem was solved by Leroy M. Kelly, a mathematician at Michigan State University. Although the problem cannot be called significant, Kelly's solution, using only eight points, is so elegant that I give it as an exercise.

The solution for the problem of placing eight points so that the perpendicular bisector of each pair of points passes through at least two other points is shown in Figure 123.

David L. Silverman's game of Slither produced a flood of strategies of steadily mounting generality until finally Ronald C. Read, a graph theorist at the University of Waterloo, reduced the standard game to monumental triviality.

ANSWERS

Figure 123

Figure 123

h"

h"

Solution to the eight point problem

Standard Slither is played on a rectangular field consisting of a square lattice of dots. Players take turns drawing orthogonal unit "edges" connecting adjacent dot pairs, adding each move to either end of the continuous path that is formed. The player who is forced to make the slithering line meet itself is the loser. Several dozen readers immediately pointed out that on the 5-by-6 field that had been given as a sample playing field, the first player has an easy win by taking the central edge and thereafter making his moves symmetrically opposite to his opponent's moves. He also wins the reverse version (the first to close the path wins) by seizing the first winning opportunity offered.

George A. Miller of Philadelphia was the first to provide a general strategy for all rectangular boards. If the field has an even number of dots, draw a Hamiltonian path along the lattice lines, that is, a path visiting every dot once only. Color the alternate edges red, beginning and ending with red. The first player's winning strategy is: Always play red. If the field contains an odd number of dots, the second player's winning strategy is: After the first move, draw any Hamiltonian path starting at one end of the first move, color the path as before and always play red. Essentially the same strategy was also discovered by Michael Kelly, by Oliver G. Selfridge, and others.

Next I found that this strategy applies if diagonal moves between adjacent dots are allowed, and also when the game is played on triangular lattices. My elation was short-lived. When I wrote to Read about it, he saw at once that these were merely special cases of a general strategy that applies to any set of dots in any formation in a space of any dimensions. Moreover, a "move" can be the joining of any pair of dots, and it does not matter whether this is allowed at both ends of the path or only at the end of the preceding move.

Read explained it this way. A graph is said to have a "1 -factor" if it is possible to join all the nodes in pairs so that every node belongs to one and only one of the disjoint edges. Think of an array of dots as the vertexes of a complete graph consisting of all possible joining edges. Draw a 1-factor of the graph with a red pencil. (A Hamiltonian path on square lattices is one way of doing this, but the 1-factor is more general because some graphs have 1-factors but no Hamiltonian path.) Any move connecting two dots is now allowed.

If the number of dots is even, the graph can be 1-factored and the first player wins by always playing on red edges. If the number of dots is odd, the second player disregards one end of the first move, 1-factors the remaining dots and plays always on red. The player who first runs out of unused dots to move to is the loser.

This obvious and trivial parity strategy was obscured in Slither by the game's many irrelevancies. Reverse Slither, in which the first to close the path wins, is a more difficult matter. As we have seen, a symmetry strategy wins for the first player on all odd-by-even fields. The second player can win by bilateral symmetry play if the first play is to a main diagonal of a square or to a central orthogonal line of any rectangle that has one. Selfridge has found a strategy for a second-player win on all squares.

Michael Beeler of M.I.T. wrote a computer program for reverse Slither. Here are some of its results:

1. The second player wins on squares through order 6.

2. Taking the center move is the only winning first play on the 3 by 4, 4 by 5, 4 by 9 and 5 by 6.

3. A theory devised by Beeler, establishing a first-player win on all 2 x n fields (n greater than 2) is confirmed through n= 18.

4. On 3 Xn fields, n = 2 through 12, the first player wins if n is even, loses if n is odd.

5. On 4Xn fields, n = 5 through 9, the first player wins in all cases.

6. The second player wins on the 5 by 7.

These data suggest the following unproved conjecture: The first player wins on all nonsquare rectangles if the number of spots is even. The second player wins on all squares and on all nonsquare rectangles if the number of spots is odd.

ADDENDUM

The 3X+ 1 problem, as it is now usually called, is still resisting solution. According to Richard Guy, it was first proposed before World War II by Lothar Collatz, now a mathematician at the University of Hamburg, when he was a student. In a 1970 lecture H. S. M. Coxeter offered $50 for a proof he could understand or $100 for a counterexample. He has since been deluged with so many false proofs that he is no longer willing to evaluate them. Indeed, it seems as easy to make subtle mistakes in such proofs as in proofs of Fermat's last theorem. False proofs have even been published; for example, in Fibonacci Quarterly, Vol. 18, 1980, pages 231-242. In 1982 Paul Erdos expressed his opinion—and who is more qualified to give one?—that if the conjecture is true, present-day number theory lacks the tools for a proof.

A counterexample would be a number that either keeps generating larger and larger numbers forever, without ever repeating a number, or one that enters a loop higher than the 4-2-1. If a counterexample exists it would have to be exceedingly large because the conjecture has been tested, according to Guy, for all numbers less than 7x 10". Early in the game it was observed that it is not necessary to test even numbers, or odd numbers of the form 4k+ 1, 16A + 3, or 128A + 7. This greatly simplifies computer programs. Of course as soon as a sequence hits a power of 2, often after many chaotic ups and downs, it crunches quickly to 4-2-1. The power of 2 on which most sequences converge is 16.

Among numbers smaller than 50, the worst is 27. After 77 steps it reaches its peak of 9,232, then 34 steps are required to take it down to 1. When John H. Conway introduces the 3X+ 1 conjecture in lectures, he likes to stand by a blackboard and say, "Let's take some random small number, say 27, and see what happens." A graph theorist would describe the theorem by saying that, if true, we can draw an infinite directed tree, each point labeled with a distinct positive integer, that will catch all the integers, and which will converge along the arrows to a root that is the triangular cycle 4-2-1.

A simple proof that of the two numbers ire and it + e, at least one is transcendental, is given by David Brubaker in Mathematics Magazine, Vol. 44, November 1971, page 267.

On triangles that can be cut into five similar triangles not similar to the original, see Guy's report in The American Mathematical Monthly, Vol. 80, December 1973, page 1123. Apparently there are ten essentially different cases. The equilateral triangle and any isosceles triangle can be cut into five similar right triangles, and the equilateral triangle can also be cut into five similar triangles containing an angle of 120 degrees.

For more on "honest numbers" that spell with the same number of letters as the number they represent (FOUR is the only honest number in English), see Chapter 7 of my Incredible Dr. Matrix.

An ultimate generalization of Slither was analyzed by William N. Anderson, Jr., in a paper listed in the Bibliography. The game is played on an arbitrary finite graph, each player taking an edge of the graph on his turn. Anderson presents a strategy for this generalized Slither that is based on a matching algorithm in a 1965 paper by J. Edmonds.

BIBLIOGRAPHY

Problems in Modern Mathematics. Stanislaw M. Ulam. John Wiley, 1960, revised edition, 1964.

Tomorrow's Math. C. Stanley Ogilvy. Oxford University Press, 1962, revised edition, 1972.

Unsolved Problems in Number Theory. Richard K. Guy. Springer-Verlag, 1981.

On the 3X+ 1 problem:

Modern Abstract Algebra. Richard V. Andree. Holt, Rinehart and Winston, second edition, 1971.

Computer Approaches to Mathematical Problems. Jiirg Nievergelt, J. Craig Farmer, and Edward M. Reingold. Prentice-Hall, 1974, pages 211— 217.

"Problem 133." Comments by Charles Trigg and others. Crux Mathe-maticorum, Vol. 2, 1976, pages 144-150.

"Crazy Roller Coaster." William J. Bruce. The Mathematics Teacher, Vol. 71, January 1978, pages 45-49.

"On the 3X+1 Problem." R. E. Crandall. Mathematics of Computation, Vol. 32, 1978, pages 1281-1292.

Godel, Escher, Bach. Douglas Hofstadter. Basic Books, 1979, pages 400-402.

"3X+1 Revisited." Fred Gruenberger. Popular Computing, Vol. 7, October 1979, pages 3—12. (Earlier references in the same periodical are cited.)

Unsolved Problems in Number Theory. Richard K. Guy. Springer-Verlag, 1981, pages 120-121.

"On the Collatz 3n+l Algorithm." L. E. Garner. Proceedings of the American Mathematical Society, Vol. 82, 1981, pages 19—22.

"The 3X+ 1 Problem and Its Generalization." J. C. Lagarias, 1982, unpublished.

On Slither:

"Slither." Anonymous. Function, Vol. 1, April 1977, page 13; October 1977, pages 15-20.

"Maximum Matching and the Game of Slither." William N. Anderson, Jr. Journal of Combinatorial Theory, Vol. 17(B), 1974, pages 234—239.

0 0

Post a comment