Recreational mathematics


The wolf, the goat, and the cabbages

Dancing alongside the more serious practitioners of mainstream mathematics are the purveyors of mathematical puzzles and problems. These go back at least as far as Diophantus (c. 200–284), the Alexandrian “father of algebra.” Alcuin of York (c. 735–804) produced a collection of problems that included the the wolf, the goat, and the cabbages (above); the three men who need to cross a river with their sisters; and problems similar to the bird puzzle published by Fibonacci a few centuries later. In more modern times, Martin Gardner (1914–2010) has done more than anyone else to popularise this offshoot of mathematics. It is often called “recreational mathematics,” because people do it for fun (in part because they are not told that it is mathematics).

Particularly popular in recent times have been Sudoku (which is really a network colouring problem in disguise) and the Rubik’s Cube (which illustrates many concepts of group theory, although it was not invented with that in mind). Sudoku puzzles have been printed in more than 600 newspapers worldwide, and more than 20 million copies of Sudoku books have been sold. The Rubik’s Cube has been even more popular: more than 350 million have been sold.


A Soma cube, assembled

Recreational puzzles may be based on networks, as in Hashi (“Bridges”). They may be based on fitting two-dimensional or three-dimensional shapes together, as in pentominoes or the Soma cube. They may be based on transformations, as in the Rubik’s Cube. They may even be based on arithmetic, as in Fibonacci’s problem of the birds, or the various barrel problems, which go back at least as far as the Middle Ages.

In one barrel problem, two men acquire an 8-gallon barrel of wine, which they wish to divide exactly in half. They have an empty 5-gallon barrel and an empty 3-gallon barrel to assist with this. How can this be done? It is impossible to accurately gauge how much wine is inside a barrel, so that all that the men can do is pour wine from one barrel to another, stopping when one barrel is empty, or the other is full [highlight to show solution → (8, 0, 0) → (3, 5, 0) → (3, 2, 3) → (6, 2, 0) → (6, 0, 2) → (1, 5, 2) → (1, 4, 3) → (4, 4, 0)]. There is a similar problem where the barrel sizes are 10, 7, and 3.


The barrels

Apart from being fun, puzzles of this kind have an educational benefit, training people to think. For this reason, Alcuin called his collection of problems Propositiones ad Acuendos Juvenes (Problems to Sharpen the Young). Problems like these may also benefit the elderly – the Alzheimer’s Association in the United States suggests that they may slow the onset of dementia. This is plausible, in that thinking hard boosts blood flow to the brain, and research supports the idea (playing board games and playing musical instruments are even better).


Advertisements

Mathematics and Art: Why can’t we be friends?


The figures of Geometry and Arithmetic by the Coëtivy Master, late 15th century (detail from Philosophy Presenting the Seven Liberal Arts to Boethius)

For most of history, mathematics and the visual arts have been friends. Art was not distinguished from what we now call “craft,” and mathematics – geometry and arithmetic – provided both a source of inspiration and a set of tools. Polykleitos, for example, in the 5th century BC, outlined a set of “ideal” proportions for use in sculpture, based on the square root of two (1.414…). Some later artists used the golden ratio (1.618…) instead.

Symmetry has also been an important part of art, as in the Navajo rug below, as well as a topic of investigation for mathematicians.


Navajo woollen rug, early 20th century (Honolulu Museum of Art)

The Renaissance saw the beginning of the modern idolisation of artists, with Giorgio Vasari’s The Lives of the Most Excellent Painters, Sculptors, and Architects. However, the friendship between mathematics and art became even closer. The theory of perspective was developed during 14th and 15th centuries, so that paintings of the time have one or more “vanishing points,” much like the photograph below.


Perspective in the Galerie des Batailles at Versailles (base image: 1890s Photochrom print, Library of Congress)

Along with the theory of perspective, there was in increasing interest in the mathematics of shape. In particular, the 13 solid shapes known as Archimedean polyhedra were rediscovered. Piero della Francesca rediscovered six, and other artists, such as Luca Pacioli rediscovered others (the last few were rediscovered by Johannes Kepler in the early 17th century). Perspective, polyhedra, and proportion also come together in the work of Albrecht Dürer. Illustrations of the Archimedean polyhedra by Leonardo da Vinci appear in Luca Pacioli’s book De Divina Proportione.


Illustration of a Cuboctahedron by Leonardo da Vinci for Luca Pacioli’s De Divina Proportione (1509)

Some modern artists have continued friendly relations with mathematics. The Dutch artist M. C. Escher (reminiscent of Dürer in some ways) sought inspirations in the diagrams of scientific publications, for example.


Tiling by M. C. Escher on the wall of a museum in Leeuwarden (photo: Bouwe Brouwer)

Today it is possible to follow in Escher’s footsteps by studying a Bachelor of Fine Arts / Bachelor of Science double degree at some institutions. There is also a renewed interest in the beauty of mathematical objects, whether three-dimensional (such as polyhedra) or two-dimensional (such as the Mandelbrot set). The role of the artist then becomes that of bringing out the beauty of the object through rendering, colouring, choice of materials, sculptural techniques, and the like.


View of the Mandelbrot set at −0.7435669 + 0.1314023 i with width 0.0022878 (image: Wolfgang Beyer)

Artistic techniques such as these (“must we call them “craft” or “graphic design”?) are also important in the field of data visualisation, and are recognised by the “Information is Beautiful” Awards. Speaking of which, this year’s awards are now open for submissions.


Sequences, R, and the Free Monoid

An important concept in computer science is the free monoid on a set A, which essentially consists of sequencesa1an⟩ of elements drawn from A. The key operations on the free monoid are:

  • a⟩, forming a singleton sequence from a single element of A
  • xy, concatenation of the sequences x and y, which satisfies the associative law: (xy)⊕z = x⊕(yz)
  • ⟨⟩, the empty sequence, which acts as an identity for concatenation: ⟨⟩⊕x = x⊕⟨⟩ = x

The free monoid satisfies the mathematical definition of a monoid, and is free in the sense of satisfying nothing else. There are many possible implementations of the free monoid, but they are all mathematically equivalent, which justifies calling it the free monoid.

In the R language, there are four main implementations of the free monoid: vectors, lists, dataframes (considered as sequences of rows), and strings (although for strings it’s difficult to tell where elements start and stop). The key operations are:

Vectors Lists Dataframes Strings
⟨⟩, empty c() list() data.frame(n=c()) ""
a⟩, singleton implicit (single values are 1-element vectors) list(a) data.frame(n=a) as.character(a)
xy, concatenation c(x,y) c(x,y) rbind(x,y) paste0(x,y)

An arbitrary monoid on a set A is a set B equipped with:

  • a function f from A to B
  • a binary operation xy, which again satisfies the associative law: (xy)⊗z = x⊗(yz)
  • an element e which acts as an identity for the binary operator: ex = xe = x

As an example, we might have A = {2, 3, 5, …} be the prime numbers, B = {1, 2, 3, 4, 5, …} be the positive whole numbers, f(n) = n be the obvious injection function, ⊗ be multiplication, and (of course) e = 1. Then B is a monoid on A.

A homomorphism from the free monoid to B is a function h which respects the monoid-on-A structure. That is:

  • h(⟨⟩) = e
  • h(⟨a⟩) = f(a)
  • h(xy) = h(x) ⊗ h(y)

As a matter of fact, these restrictions uniquely define the homomorphism from the free monoid to B to be the function which maps the sequence ⟨a1an⟩ to f(a1) ⊗ ⋯ ⊗ f(an).

In other words, simply specifying the monoid B with its function f from A to B and its binary operator ⊗ uniquely defines the homomorphism from the free monoid on A. Furthermore, this homomorphism logically splits into two parts:

  • Map: apply the function f to every element of the input sequence ⟨a1an
  • Reduce: combine the results of mapping using the binary operator, to give f(a1) ⊗ ⋯ ⊗ f(an)

The combination of map and reduce is inherently parallel, since the binary operator ⊗ is associative. If our input sequence is spread out over a hundred computers, each can apply map and reduce to its own segment. The hundred results can then be sent to a central computer where the final 99 ⊗ operations are performed. Among other organisations, Google has made heavy use of this MapReduce paradigm, which goes back to Lisp and APL.

R also provides support for the basic map and reduce operations (albeit with some inconsistencies):

Vectors Lists Dataframes Strings
Map with f sapply(v,f), purrr::map_dbl(v,f) and related operators, or simply f(v) for vectorized functions lapply(x,f) or purrr::map(x,f) Vector operations on columns, possibly with dplyr::mutate, dplyr::transmute, purrr::pmap, or mapply Not possible, unless strsplit or tokenisation is used
Reduce with ⊗ Reduce(g,v), purrr::reduce(v,g), or specific functions like sum, prod, and min purrr::reduce(x,g) Vector operations on columns, or specific functions like colSums, with purrr::reduce2(x,y,g) useful for two-column dataframes Not possible, unless strsplit or tokenisation is used

It can be seen that it is particularly the conceptual reduce operator on dataframes that is poorly supported by the R language. Nevertheless, the map and reduce operations are both powerful mechanisms for manipulating data.

For non-associative binary operators, purrr::reduce(x,g) and similar functions remain extremely useful, but they become inherently sequential.

For more about purrr, see purrr.tidyverse.org.


Mathematics in Action: Vehicle Identification Numbers

Motor vehicles have a 17-character Vehicle Identification Number or VIN on a metal plate like the one below, usually on the driver’s side dashboard, or on the driver’s side door jamb, or in front of the engine block:


A Vehicle Identification Number (VIN) plate (Photo: Michiel1972)

VINs offer an interesting example of check digit calculation. The central digit (or an X representing 10) is a check digit (calculated modulo 11) used to detect errors. Any letters in the rest of the VIN are decoded like this:

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
1 2 3 4 5 6 7 8 1 2 3 4 5 7 9 2 3 4 5 6 7 8 9

The check digit calculation involves decoding the VIN, and multiplying the resulting numbers by the weights shown in blue, giving the products in purple:

VIN L J C P C B L C X 1 1 0 0 0 2 3 7
Decoded 3 1 3 7 3 2 3 3 10 1 1 0 0 0 2 3 7
Weights 8 7 6 5 4 3 2 10 0 9 8 7 6 5 4 3 2
Product 24 7 18 35 12 6 6 30 0 9 8 0 0 0 8 9 14

These products are added up modulo 11 (meaning the sum is divided by 11 and the remainder taken). In this case, the sum is 186 = 10 = X (mod 11), which makes the VIN valid, because it matches the original central X. What about the VIN on your vehicle?


The Sand Reckoner

In his short work The Sand Reckoner, Archimedes (c. 287 BC – c. 212 BC) identifies a number larger than what he believed was the number of grains of sand which would fit into the Universe. He was hampered by the fact that the largest number-word he knew was myriad (10,000), so that he had to invent his own notation for large numbers (I will use modern scientific notation instead).

Archimedes’ began with poppyseeds, which he estimated were at least 0.5 mm in diameter (using modern terminology), and which would contain at most 10,000 grains of sand. This makes the volume of a sand-grain at least 6.5×10−15 cubic metres (in fact, even fine sand-grains have a volume at least 10 times that).

Archimedes estimated the diameter of the sphere containing the fixed stars (yellow in the diagram below) as about 2 light-years or 2×1016 metres (we now know that even the closest star is about 4 light-years away). This makes the volume of the sphere 4×1048 cubic metres which means, as Archimedes shows, that less than 1063 grains of sand will fit.

A more modern figure for the diameter of the observable universe is 93 billion light-years, which means that less than 1095 grains of sand would fit. For atoms packed closely together (as in ordinary matter), less than 10110 atoms would fit. For neutrons packed closely together (as in a neutron star), less than 10126 neutrons would fit. But these are still puny numbers compared to, say, 277,232,917 − 1, the largest known prime!


Snakes and Ladders


Snakes and Ladders board, dated 1966, from the Auckland Museum (credit)

Snakes and Ladders is an ancient board game originating in India. It is totally random, and hence not very interesting. If players start on square #1, then after one turn, they have equal probabilities of being on squares #2, #3, #4, #5, #6, and #7. This image shows the probability distribution:

After two turns, the probability distribution is as follows (the most likely total of two dice rolls is 7, taking a player to square #8 and up a ladder to #26:

After 8 turns, players would be scattered all over the board. There is a 1% chance that any given player has won:

After 19 turns, there is a 24.7% chance that any given player has won:

This probability grows to 50.4% after 35 turns. But no matter how long you play, it remains possible (though increasingly unlikely) that nobody has won yet. Yet another reason why children tend to rapidly tire of the game.

For an alternative view of the probability analysis, see this animation:


The Game of Mu Torere

The New Zealand game of mū tōrere is illustrated above with a beautiful handmade wooden board. The game seems to have been developed by the Māori people in response to the European game of draughts (checkers). Play is quite different from draughts, however. The game starts as shown above, with Black to move first. Legal moves involve moving a piece to an adjacent empty space:

  • along the periphery (kewai), or
  • from the centre (pūtahi) to the periphery, or
  • from the periphery to the centre, provided the moved piece is adjacent to an opponent’s piece.

Game play continues forever until a draw is called (by mutual consent) or a player loses by being unable to move. Neither player can force a win, in general, so a loss is always the result of a mistake. For each player there is one “big trap” and four “small traps.” This is the “big trap” (Black wins in 5 moves):

  
The board on the left is the “big trap” for White – Black can force a win by moving as shown, which leaves only one move for White.

  
Again, Black moves as shown, which leaves only one move for White.

  
Now, when Black moves as shown, White cannot move, which means that White loses.

Here is one of the four “small traps” for White. The obvious move by Black results in White losing (but avoiding this does not require looking quite so far ahead as with the “big trap”):

Here (click to zoom) is the complete network of 86 game states for mū tōrere (40 board positions which can occur in both a “Black to move” and a “White to move” form, plus 6 other “lost” board positions). Light-coloured circles indicate White to move, and dark-coloured circles Black to move, with the start position in blue at the top right. Red and pink circles are a guaranteed win for Black, while green circles are a guaranteed win for White. Arrows indicate moves, with coloured arrows being forced moves. The diagram (produced in R) does not fully indicate the symmetry of the network. Many of the cycles are clearly visible, however: