On April 11, 2020, John Horton Conway died of COVID-19 at the age of 82 in New Brunswick, N.J. The areas of research covered by this remarkable mathematician included group theory, node theory, geometry, analysis, combinatorial game theory, algebra, algorithmics and even theoretical physics.
Conway’s inclinations and talent led him to invent a remarkable cellular automaton called the Game of Life, which continues to fascinate after 50 years. Conway also devised elegant puzzles for packing boxes of blocks that can only be solved efficiently with clever reasoning.
According to Conway, his most important contribution was his conceptualization of a marvelous system of numbers called surreal numbers. This class comprises integers, real numbers, transfinite numbers and infinitesimals—a structure that no one previously imagined was possible in which everything can be added, multiplied, and so on.
People who worked with Conway report that he thought so fast that no sooner did he hear a problem stated than he often already had a solution. Conway’s commitment to mathematics for everyone led him to work on puzzles that delight fans of recreational mathematics, such as the famous Collatz conjecture (which is discussed toward the end of this article).
Conway was the mathematician most cited (more then 30 times!) in my columns in Pour la Science, the French edition of Scientific American. In preparing the articles, I would often come across a result he had demonstrated or an important idea that he had been the first to propose on the topic, much to my surprise. Conway liked simple, practical mathematical problems that called on his creativity.
The best way to honor him, it seems to me, is to highlight the kind of mathematics that amazed and fascinated him. I am going to cover several different topics to which Conway contributed. But it would take several volumes to do justice to this exceptional mind. He was able to invent objects and problems in many different domains and to solve the most recalcitrant puzzles, conceiving methods no one could have imagined.
The Irrationality of √2
One of the most surprising and important mathematical findings is the irrationality of the square root of 2 (√2)—the length of the diagonal of a square with sides that are one unit long. It cannot be expressed by the quotient of positive integers n and m, or n/m. The discovery of the irrationality of √2 is credited to Pythagoras or one of his disciples, although we do not know whether the reasoning behind it was arithmetic or geometric. The discovery and its proof were profoundly unsettling for mathematicians. This first negative finding in mathematics showed that humans do not create the laws governing numbers but rather uncover them as they explore uncharted mathematical territory.
Though there are many proofs of this theorem, the most intuitive is a very simple little drawing that Conway included in a lecture published in a book in 2005. He attributed the creation of the proof to mathematician Stanley Tennenbaum, who, according to Conway, had abandoned mathematics. You might ask whether it was Conway himself who formulated the proof. But that does not matter. Because even if he did not create it, the proof offers a perfect example of Conway’s approach to mathematics, which he demonstrated in 100 different ways. It also shows that it is wrong to believe that everything simple has already been discovered: brilliant yet astonishingly simple ideas are still waiting to be revealed.
Say that √2 is the quotient of n and m—that is, 2 = n2/m2, or 2m2 = n2. If so, there exists a square, with sides equal to n, whose area equals twice that of a square with sides equal to m [see part A of “An Irrational Square Root”]. We assume that in our drawing, m is the smallest positive integer satisfying this equation. The assumption would be valid only if there is no smaller positive integer that satisfies it.
Wedging the two blue squares into two diagonally opposite corners of the red square produces a new shape. The two red squares in that shape must have the same area as the central purple square that is created where the two blue squares overlap [see Part B of “An Irrational Square Root”].
Our reasoning requires that the area of the two blue squares must be equal to the area of the red one (A). Consequently, the area not covered by the two blue squares is equal to twice the area covered by both of them. In other words, there are two equal and smaller squares (red, B) that together have the same area as the larger square (purple, B). That means each side of the new small squares is equal to the integer n – m, and each side of the large purple square is equal to the integer n – 2(n – m) = 2m – n.
In short, the initial square of side m was not the smallest possible one that satisfies the geometric equation. The result is a contradiction, and thus the assumption is false: √2 is not a quotient of two integers, which means it is an irrational number. In the same way, you can demonstrate that the square root of 3 is irrational [see part C of “An Irrational Square Root”].
Three Cube-Packing Puzzles
Many puzzles consist of putting a small number of blocks in a box (say 10). Both the blocks and the box are typically rectangular parallelepipeds. The solution is usually arrived at by trial and error. With a problem like this one, unless you increase the number of blocks and their variety of shapes, it is hard to conceive a challenging puzzle. Moreover, although it can be fun to manipulate the blocks until the solution is found, doing so involves only a little reasoning about shape and thus does not really reduce the solution time.
Conway reimagined the problem by creating puzzles that can potentially lead you in circles while you try to figure out how to fill the box. But a few astute and orderly considerations will quickly guide you to the solution.
The simplest of these three puzzles consists of filling a 3 x 3 x 3 box with three 1 x 1 x 1 cubes and six 1 x 2 x 2 parallelepipeds [see part 1 of “Blocks in a Box”].
The reasoning consists of taking parity into account: The 3 x 3 x 3 box is composed of three horizontal 3 x 3 x 1 layers, each with a volume of 9. The 3 x 3 x 3 box can also be decomposed into three vertical 3 x 3 x 1 parallelepipeds, each parallel to a vertical face of the box. Considering the perpendicular vertical face produces a third decomposition of the box into three 3 x 3 x 1 parallelepipeds.
Let’s examine these nine parallelepipeds. When a 1 x 2 x 2 block is positioned in the box, it can only fill an even number of the nine cells in each 3 x 3 x 1 layer. So each layer must contain one—and only one—of the three small 1 x 1 x 1 blocks (otherwise you would have to place all three of them in a single 3 x 3 x 1 layer, which would leave none in the other two layers, where they are needed). The upper layer of the box must therefore contain one 1 x 1 x 1 block. If we place it in the center of the layer, we quickly reach a dead end, because we are obliged to place another small block just below it. That puts two of them in a single 3 x 3 x 1 vertical layer. Placing the small block on the top face in the middle of any side also results in an impasse. Consequently, the small block on the top layer must go in a corner.
The same reasoning applies to the bottom layer, where a small block must be placed in a corner. That corner must be diametrically opposite to the small block on the top layer. The third small block must therefore go in the center of the middle layer. The remaining steps become quickly obvious. Note that this reasoning not only produces a solution but also shows that, except for symmetries, there is only one solution.
The solution to another of Conway’s packing problems is shown in part 2 of “Blocks in a Box.” To complete the packing, all you have to do is to lower the two upper structures and place the green layer (b) at the side on top of the pink layer (a). Reasoning based on parity forces us to place the unit cubes along the diagonal.
The Riddle of the Two Wizards
In the 1960s Conway devised a fiendishly tricky puzzle that, until recently, prompted much debate and the publication of a paper by Tanya Khovanova of the Massachusetts Institute of Technology in 2013. Here is the puzzle as it appears in that paper:
Last night I sat behind two wizards on a bus, and overheard the following:
A: “I have a positive integral number of children, whose ages are positive integers, the sum of which is the number of this bus, while the product is my own age.”
B: “How interesting! Perhaps if you told me your age and the number of your children, I could work out their individual ages?”
A: “No.”
B: “Aha! AT LAST I know how old you are!”
Now what was the number of the bus?
Note that in the exchange, the “no” uttered by Wizard A does not mean that he refuses to answer but that the knowledge of his age and the number of his children does not make it possible to know their individual ages. Of course, you have to assume that Wizard B knows the number of the bus. Note, too, that the wizards can be very young or very old: Wizard A could well be two or 20,000 years old.
Here is the solution, which I was only able to fully understand and verify with the help of a program. I can’t reproduce all the calculations required for the conclusion, but you can take my word for it —or redo all the calculations I’ve left out.
Let us denote the age of Wizard A as a, the number of the bus as b and the number of Wizard A’s children as c. Suppose, for example, that the number of the bus is b = 5. The following are the options for the number of children, the distribution of their ages and the age of Wizard A:
- c = 5 of ages 1, 1, 1, 1, 1; thus, a = 1;
- c = 4 of ages 1, 1, 1, 2; thus, a = 2;
- c = 3 of ages 1, 1, 3; thus, a = 3;
- c = 3 of ages 1, 2, 2; thus, a = 4;
- c = 2 of ages 1, 4; thus, a = 4;
- c = 2 of ages 2, 3; thus, a = 6;
- c = 1 of age 5; thus, a = 5.
In each case, knowing the age of Wizard A and the number of children indicates the possible ages of the latter. Because Wizard A answered “no” and Wizard B knows the number of the bus, this means b is not equal to 5.
Similarly, you can solve the problem by examining the possible bus numbers one by one to find those for which knowing the age of the wizard and the number of his children will not enable you to know the ages of each of the children (a property we denote as P). Calculating b = 1, 2, 3, ..., 12 (as we have just done for b = 5) shows that b = 12 is the smallest number possessing P.
Indeed, for b = 12 and c = 4, there are two sets of possible ages of the four children—(2, 2, 2, 6) and (1, 3, 4, 4)—which both give the same age for Wizard A: a = 48. No other two sets of the same length with the same product for b = 12 exist. Therefore, for b = 12, even knowing that c = 4 and a = 48, it is impossible to deduce the ages of the four children. Does this mean that b = 12 is the solution?
Unfortunately, not yet. For bus number b = 13, for example, because the two possible sets of the three children’s ages—(1, 6, 6) and (2, 2, 9)—are both compatible with a = 36, Wizard B cannot derive the ages of Wizard A’s children from the knowledge of either his age or the number of his children.
Knowing that b = 12 is no more conclusive about the ages of the children than knowing that b = 13. When confronted with the puzzle, most people often answer “b = 12,” as if the riddle somehow implies that the smallest possible solution for b is the right one. But the puzzle does not make that assertion. Moreover, without further reasoning, you cannot choose between b = 12 and b = 13, nor can you choose among other values of b, as my further calculations show.
Yet b = 12 is the correct answer, and the reason for that is the most interesting and unexpected part of the riddle. Conway crafted his puzzle carefully, and you must consider the final statement of Wizard B. Following Wizard A’s “no,” Wizard B responds, “Aha! AT LAST I know how old you are!” That eliminates b = 13.
In fact, for b = 13, there are two additional sets of the children’s ages—(1, 2, 2, 2, 6) and (1, 1, 3, 4, 4)—that give a = 48. In other words, if the bus number were 13, Wizard B could not deduce the age of Wizard A from his negative answer because his age could be 36 or 48. Thus, b = 13 should be eliminated.
Yet eliminating b = 13 leads to the elimination of b = 14 when we consider the age sequences found for b = 13 and add 1. Doing so shows that the product of two sets of the children’s ages—(1, 1, 6, 6) and (1, 2, 2, 9)—is a = 36, whereas the product of another two sets—(1, 1, 2, 2, 6) and (1, 1, 1, 3, 4, 4)—is a = 48. The same process eliminates b = 15 and, one by one, all of the b’s greater than 12.
Consequently, it is only bus number 12 (b = 12), with two sets of the children’s ages—(2, 2, 2, 6) and (1, 3, 4, 4)—that uniquely determines the age of Wizard A: a = 48.
Given all the calculations you’d have to do to arrive at the solution—the details of which I have not reproduced here and which take up several pages—I confess that I don’t understand how Conway managed to conceive this incredible puzzle!
Paving a Plane with Line Segments
Paving a plane with squares is easy. It is just as easy to do so using equilateral triangles or hexagons. It is also possible to pave the plane with infinite straight lines: just place them all side by side and parallel. There will be an infinite number of them, but the paving will be perfectly satisfactory because each point of the plane will belong to one —and only one—line of the paving. Here are a few trickier questions:
- Can the plane be paved with closed segments—i.e., straight line segments [A, B], including their endpoints?
- Can the plane be paved with open segments—i.e., segments ]A, B[, without their endpoints?
- Can the plane be paved with semi-open segments—i.e., segments ]A, B], with only one of their endpoints?
Think about these unusual yet perfectly natural questions. They are not so simple. Conway and a colleague discussed them and other types of problems in a splendid paper published in 1964, proving once again that very simple questions that no one thinks about are great opportunities to do mathematics that is not so obvious.
In that paper, Conway and mathematician Hallard Croft devised a way to fill a plane with straight line segments, which can be seen in “Fine Paving” below.
Panel a shows how to pave a plane with semi-open segments in which one point is included and another is excluded. Doing so is easy because placing them together, head to tail, reproduces the obvious paving with straight lines.
Panel b shows the solution for equal closed segments in which both points of each segment are included. Pillar 1 is placed first. Pillar 2 is then added, but of course the leftmost segment of this stack is not retained. For pillar 3, the rightmost segment is not retained. Ever finer slanted pillars are added successively, omitting the “first” segment for each.
Panel c shows a solution for differently sized open segments (with their endpoints excluded). The segments create a central square open on all sides—i.e., neither the sides nor the top or bottom of the square are covered. Each successively added rectangle is also open. For open segments of the same length, there is no solution for paving the plane.
The Collatz Conjecture
Another puzzle is as interesting to amateur mathematicians as it is to professionals. Consider a function (f) that gives n/2 for positive integers (n) that are even and 3n + 1 for those that are odd. For example, starting with 7 and applying f, you get 22, then 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1, 4, 2, 1, and so on. Once you get to 1, you go around in circles.
Whatever integer n you start with, you always seem to end up at 1 and then get stuck in a loop. Computer calculations have tested this property, which is true for all n’s up to at least 87 x 260 (about 1020). It has not been proved, however, that this is always the case, nor has an initial n been found that would continue to infinity or lead to a cycle other than 4, 2, 1.
This problem is called the Collatz conjecture or the Syracuse conjecture. Much work has been devoted to it, some of which has been compiled in a book. The great simplicity of the problem’s statement attracts amateurs, and I regularly receive proposed solutions that, to date, are either wrong or incomprehensible.
Faced with such a challenge—so simply stated and yet unsolved, which is still the case after more than 80 years—Conway could not resist.
In 1972 he published his first paper on the subject, in which he proposed similarly formulated problems and demonstrated their undecidability. For certain values of the starting integer, the sequence generated by the variant of f does not end up arriving at 1, but set theory cannot demonstrate this. More generally, for any logical system of demonstration (S), there is a problem of this category and a starting point for a sequence that does not end up at 1, which cannot be demonstrated by S.
In 2013 Conway returned to the problem with probabilistic arguments suggesting that the Collatz conjecture itself is unprovable with the axiom systems that are usually used in mathematics. This was not a definitive demonstration of the undecidability of the Collatz conjecture. But the types of arguments he proposed seemed to strongly indicate that it is no accident that everyone stumbles in their attempt to prove the conjecture.
All mathematicians encounter problems they cannot solve, and Conway was no exception to this general rule. Nevertheless, his skill as a logician may have afforded some comfort by enabling him to demonstrate undecidability and to elaborate arguments suggesting that this simple yet intractable problem would continue to challenge mathematicians indefinitely.
A New Pattern in the Game of Life
The Game of Life, first introduced in Martin Gardner’s Mathematical Games column in Scientific American in 1970, is still being studied, and all of the puzzles that it poses have not been solved. A square cell in an infinite, two-dimensional rectangular grid may be alive or dead. Or the cell may go from live (black) to dead (white), or vice versa, from one generation to another. Or the cell may remain stable, depending on whether its eight nearest neighbor cells are dead or alive.
The rule of evolution can be expressed in 12 words: birth if three live neighbors; survival if two or three live neighbors. Some patterns with few live cells at the initial state grow to infinity. Ideally, the number of live cells increases proportionately with n2, where n is the number of the generation. The optimal density of living cells in a stable part of the grid is 1/2. Noam Elkies of Harvard University demonstrated the proof in 29 pages in 1997.
The extraordinary pattern shown at the top of “Game of Life Redux” was discovered in April 2020 by computer scientist Mateusz Naściszewski. It is the smallest known pattern that, once launched, grows quadratically to cover the grid of a stable live cell population of density 1/2. (This pattern is thus the best possible one in terms of speed and density.) The configuration begins with a population of 183 cells. We drew generation 0 and two other generations at different scales [see bottom patterns in “Game of Life Redux”]. It is believed to be impossible to do better than 183, but that has not been demonstrated. Note, too, that there are patterns that calculate the prime numbers or that even display graphic images of decimal digits of π = 3.14159... one after the other.
This article originally appeared in Pour la Science and was reproduced with permission.
"some" - Google News
April 28, 2021 at 05:45PM
https://ift.tt/3vDPDW3
For Math Fans: Some Puzzles from Game of Life Creator John Conway - Scientific American
"some" - Google News
https://ift.tt/37fuoxP
Shoes Man Tutorial
Pos News Update
Meme Update
Korean Entertainment News
Japan News Update
Bagikan Berita Ini
0 Response to "For Math Fans: Some Puzzles from Game of Life Creator John Conway - Scientific American"
Post a Comment