(20100523) Martin Gardner (19142010). Eulogy.
Born on Oct. 21, 1914, Martin Gardner passed away on May 22, 2010.
After a brief illness, Martin Gardner died unexpectedly at
Norman
Regional Hospital at the age of 95.
The precise cause of death is unknown. His passing was quick and painless.
Martin Gardner is survived by two sons: James
(of Norman, Oklahoma)
and Tom (of Asheville, NC).
He is mourned by many friends and countless professional or amateur mathematicians.
The passing of Martin Gardner has urged a few people who had crossed his path to recollect
those precious moments:
An
interview with Martin Gardner on February 28, 1979 (with Stan Ulam, Ron Graham,
Peter Renz and Don Albers)
posted in The Back Bench by Tony Barcellos (20100523)
(20090204) Hexaflexagons (1939)
Gardner's first column in Scientific American
(1956).
In 1939, Arthur Harold Stone
(19162000) was a British doctoral student who
had just arrived at Princeton University to study general topology.
Since American sheets of paper were wider than European ones,
he was trimming lettersize American sheets to fit British binders.
(The European size was not yet standardized as "A4".)
Stone was left with lots of strips of paper to fold and play with.
One day, he stumbled upon a
flexagon and showed it to some of his fellow students, including
Bryant Tuckerman (19152002),
Richard P. Feynman (19181988) and
John W. Tukey (19152000).
They formed the Princeton Flexagon Committee.
Soon, it seems everyone on campus was making and flexing hexaflexagons.
Martin Gardner, 1960
In December 1956, the hexaflexagon craze got a fresh start
when Martin Gardner sold an article about it to
Scientific American.
The publisher of Scientific American, Gerry Piel, immediately entrusted Gardner
with a monthly column: Mathematical Games,
premiered in January 1957 and lasted for more than 25 years.
(20090107) From Dominoes to Polyominoes
The 12 pentominoes of Sol Golomb (1954).
Polyominoes were devised in 1954 by
Solomon W. Golomb
when he was a 22year old graduate student at Harvard.
A polyomino
consists of N unit squares in the plane, each sharing at least
one of its sides with another square.
According to the wording of that simple definition, there is one zeromino
(consisting of an empty set of unit squares)
but there are no monominoes
(N=1). However, many
people consider a lone square to be a monomino...
Two polyominoes are considered distinct only if they cannot be
obtained from each other by rotating or flipping.
There is only one domino (N=2) but there are 2 triominoes,
5 tetrominoes, 12 pentominoes, 35 hexominoes, etc.
The set of 12 pentominoes proved to be most endearing...
Those twelve pieces are used in a twoplayer game
(proposed by Golomb himself in December 1994) which is
played on an 8 by 8 chessboard:
The players alternate placing a piece until one of them is unable to do so
(and is declared the loser).
Pentominoes have been marketed whose thickness is the same as the side of
the constituent squares. Twelve such pieces have a combined volume
of 60 cubic units, which can be assembled into 3 types of cuboids
(2 by 3 by 10, 2 by 5 by 6, 3 by 4 by 5).
(20090110) Piet Hein's Soma Cube
Nonconvex solids consisting of 3 or 4 cubes.
The 3D equivalents of polyominoes are solids consisting
of unit cubes which share at least one face with another cube.
Two such shapes are distinct only if they're not congruent by rotation.
7 distinct nonconvex shapes can be obtained in this way with 4 cubes or less
(only one consists of just 3 cubes).
This includes two chiral pieces which are mirror images
of each other. Those are the socalled soma pieces
whose combined volume is 27 units.
They can be assembled into a cube 3 units on a side.
Legend has it that the Soma Puzzle was devised by
Piet Hein (19051996)
during a lecture on quantum mechanics by
Werner Heisenberg (19011976).
(20090117) Aperiodic Penrose Tilings (1977)
Matching the colors of the kite and dart tiles.
The two Penrose tiles are quadrilaterals consisting of two pairs of equal
sides whose lengths are in a golden ratio :
f = 1.6180339887498948482...
This yields angles that are multiples of
p/5 and allow various types
of pentagonal patterns around any vertex where several tiles
meet (without voids).
The convex tile is called a kite,
the other one is dubbed dart.
They bear a specific color pattern like the one pictured above.
The colors must match along any side where two such tiles touch.
It's nice to have circular arcs centered on vertices
for the inner boundaries between colors but
more creative designs can be used, as long as the colors on equal sides
enforce the same matching as what's illustrated here.
Another (colorless) alternative would be to enforce the sidematching with
jigsawtype notches.
(20090105) Ambigrams
The inversions of Scott Kim (1981).
Scott Kim
is a friend of Martin Gardner who practices an elaborate type of
calligraphy
where the spellings of words changes when they are rotated or viewed in a mirror.
The example at right has mirror symmetry whereas the title
of this page is symmetric with respect to its central point.
(20090102)
Survival in Conway's Game of Life Any computable query boils down to
that question!
If you learn to be good at a game, you find
what it is you should have been thinking about. John
Horton Conway^{ } (1937)
The Game of Life (GOL) invented by John H.
Conway (in 1970) is a zeroplayer game.
Once a board configuration is set up, it just evolves according
to fixed rules, like life would unfold in a
completely deterministic universe.
The point is to discover life forms
with an interesting evolution...
A very rich catalog was eventually compiled
which provided a few components that allow the
simulation of any imaginable deterministic computer!
In Conway's game,
the board is just an infinite grid of square cells.
Each cell is either dead (empty) or alive (occupied
by a black dot).
The neighbors of a cell are the 8 cells
which share a side or a corner with it. There are just two rules which
govern the evolution of a configuration from one generation to the next:
A cell survives
if and only if it has either 2 or 3 live neighbors.
A cell is born [in empty space]
if and only if it has 3 live neighbors.
The socalled block is the simplest stable
life form. It consists of four live cells in a square
configuration.
Each of them survives because of its 3 live neighbors and no cell is
born because no other cell has 3 live neighbors.
The blinker consists of a row of 3 live cells which
oscillates between a vertical and a horizontal configuration.
The center cell survives, both extremities die and two cells are born
which replace them at a right angle... Again and again.
The most interesting of the small life forms is the
glider, which consists of 5 live cells and moves
diagonally one unit in 4 steps:
Spaceships :
The life patterns which move p cells in q generations
are called spaceships
and are said to be moving at p/q times
the speed of light (c). The aforementioned
glider moves at c/4 diagonally.
At right, is the dart spaceship which moves at c/3.
It was discovered by David Bell in May 1992.
Three small spaceships were discovered by Conway (in 1970)
which move at speed c/2
(namely: 2 cells in 4 generations)
either horizontally or vertically: The small fish
(or float)
the medium fish and the big fish.
They are also respectively known as the lightweight,
middleweight
and heavyweight spaceships
(abbreviated LWSS, MWSS, HWSS).
Gardens of Eden :
One early question about the Game of Life
was the existence of board configurations which cannot result from
the evolution of a previous population.
Such a configuration is known as a Garden of Eden.
The existence of Gardens of Eden can be demonstrated by the
following numerical argument:
A population contained in a square which is 5n2 cells on a side
has either no parent or at least one parent fully contained in a 5n by 5n square.
Such parent configurations can be partitioned into
5 by 5 squares. The key remark is that two parents clearly have
the same children if one of those small squares is either empty
or has only its central cell occupied.
So, the number of distinct children
of parents contained in a 5n by 5n square is
no greater than :
( 2^{25}  1 )^{ n2}
If that number is less than the number of 5n2 by 5n2 configurations, some of
those must have no parent !
Let's simplify the relevant inequality:
( 2^{ 25}  1 )^{ n2}
<
2^{ (5n2)2}
With k = lg ( 2^{ 25}  1 )
= 24.999999957004336643612528...
this inequality becomes
(taking the binary logarithm of both sides):
k n^{2}
<
25 n^{2}
 20 n + 4
The leading term of the polynomial
(25k) n^{2}
 20 n + 4 being positive, it is itself positive
for sufficiently large values of n.
Numerically, the inequality holds when n
is beyond 465163191.59...
So, there must be Gardens of Eden among
the populations contained in a square 2325815956 cells on a side!
The above can be used to show that a (very) large configuration is most likely to be
a Garden of Eden (the probability that it isn't vanishes exponentially as
a function of its size).
It's still a challenge to find small Gardens of Eden, though.
The first explicit
Garden of Eden
to be discovered was the following pattern,
inscribed in a 9 by 33 rectangle.
It was found by Roger Banks, Mike Beeler, Rich Schroeppel et al. at MIT in 1971.
Curiously,
Achim Flammenkamp
noticed many years later
(on June 16, 2004) that the 5 rightmost columns of
this historical example are essentially not needed
(yielding a 9 by 28 Orphan ).
At this writing, the smallest known Garden of Eden is a pattern
of 72 live cells in an 11 by 12 rectangle.
It was discovered by
Achim
Flammenkamp on June 23, 2004.
R. William Gosper
The Gosper Glider Gun :
Early on,
Conway had conjectured that there were finite life forms
which would grow indefinitely but he could not find one...
So, he put up a $50 reward for an example.
Bill Gosper (1943)
claimed the prize with the following grand thing,
obtained by studying the interaction of two queen bee
shuttles (stabilized by blocks ).
This was the first example of what's called a glider gun.
The Gosper gun emits a steady stream of gliders but
its core returns to its former self after 30 steps.
Glider guns have since been devised for any arbitrary period
above 14.
They are a key ingredient in the socalled universalization
of the game of life performed independently by Gosper and by Conway
(using the same approach).
As described in the next section, this establishes, essentially, that
anything boils down to a question about Conway's game!
Conway's Game of Life is a universal computer :
In the last chapter of the first edition of Winning Ways (1982)
John Conway proves that his automaton is just as powerful as a
Turing Machine
(or any other type of computer with an unbounded amount of read/write memory).
Remarkably, an engineering approach is used to show how all the components
of modern computer circuitry can be simulated within the Game of Life
(program and input data being encoded in the starting configuration).
Basically, Conway uses clocked
streams of rarefied gliders as the basic
digital signals (the presence or absence of a glider in a stream
at a scheduled time is interpreted as a specific bit being 1 or 0).
Such streams are produced by guns and absorbed by eaters
(guns with arbitrarily low output rate exist, so that synchronized
wires will not interact as they cross each other).
Conway uses a large zoo of special configurations and a bunch of
clever techniques to simulate logic gates and all the circuitry of a
finite computer endowed with an unbounded external memory which
it can read and write...
As a beautiful final touch, he shows how such a simulation can
completely selfdestruct
to indicate that the corresponding computer program has halted (otherwise,
something remains on the board).
The engineering details are quite intricate but the guiding principles are simple and the
glorious conclusion is inescapable:
The Game of Life is an automaton which is just as powerful
as a Turing machine.
Any problem which (like most interesting logical questions)
is equivalent to the ultimate halting of a computing machine
(with unlimited storage capabilities)
can actually be rephrased
in terms of the ultimate vanishing of a specific starting configuration
in Conway's Game of Life .
In other words: Life is hard.
John Conway Talks About the Game of Life
Part 1

Part 2
(20090114) Rubik's Cube: The Craze
Martin Gardner's cover story (March 1981).
The notation which is now standard to describe sequences of moves
in Rubik's cube was invented by David Singmaster in 1979.
A capital letter indicates a clockwise rotation of a quarter turn.
The same letter primed denotes a counterclockwise rotation.
The following six letters are used, which refer to the location of the
center of rotation, irrespective of its color:
F (front), R (right), L (left), U (up), D (down) and B (back).
You are allowed to lie a little,
but you should never mislead. Paul R. Halmos (19162006)
2 minutes and 53 seconds
into the aforementioned video
presented by David Suzuki (CBC, 1996) John Conway says:
This, I'm sure, was in Martin's column sometime.
You know, it's impossible to tie a knot without leaving
go of the ends of the strings the way I just did...
Up to this point, Conway did not lie but he did mislead...
Indeed, the last thing he said could be parsed as
applying only to the locution "leaving go of the ends of the strings"
(which is precisely what Conway did, secretly).
This perfect example of a
misleading true statement
is followed by Conway's concluding remark which either turns the whole thing
into a straight lie (expected of an illusionist, amateur or not)
or can be forcefully reparsed into a true statement. Your pick:
... but Martin will tell you many different ways of doing it.
Conway's performance is flawless and well photographed.
Even if you know what to look for and play the video frame by frame,
you simply won't detect the fallacy.
(20100611) The knowledge of Man
Martin Gardner loved the following Indian legend.
He first run across it in
The People, Yes (1936)
by Carl Sandburg (18781967):
The white man drew a small circle in the sand
and told the red man,
"This is what the Indian knows,"
and drawing a big circle around the small one,
"This is what the white man knows."
The Indian took the stick and swept an immense ring around both circles:
"This is where the white man and the red man know nothing."