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

The three men and their sisters

The medieval Propositiones ad Acuendos Juvenes (“Problems to Sharpen the Young”) is attributed to Alcuin of York (735–804), a leading figure in the “Carolingian Renaissance.” He is the middle person in the image above.

Along with the more famous problem of the wolf, the goat, and the cabbage, Propositiones ad Acuendos Juvenes contains the problem of the three men and their sisters. Three men, each accompanied by a sister, wish to cross a river in a boat that holds only two people. To protect each woman’s honour, no woman can be left with another man unless her brother is also present (and if that seems strange, remember that Alcuin was writing more than 1,200 years ago). In Latin, the problem is:

“Tres fratres erant qui singulas sorores habebant, et fluvium transire debebant (erat enim unicuique illorum concupiscientia in sorore proximi sui), qui venientes ad fluvium non invenerunt nisi parvam naviculam, in qua non potuerunt amplius nisi duo ex illis transire. Dicat, qui potest, qualiter fluvium transierunt, ne una quidem earum ex ipsis maculata sit?”

The diagram below (click to zoom) shows the state graph for this problem. The solution is left (per tradition) as an exercise for the reader (but to see Alcuin’s solution, highlight the white text below the diagram).


Solution:
Miss A and Mr A cross
Mr A returns (leaving Miss A on the far side)
Miss B and Miss C cross
Miss A returns (leaving Misses B and C on the far side)
Mr B and Mr C cross
Mr B and Miss B return (leaving Miss C and Mr C on the far side)
Mr A and Mr B cross
Miss C returns (leaving 3 men on the far side)
Miss A and Miss C cross
Mr B returns (leaving the A’s and C’s on the far side)
Mr B and Miss B cross


Looking back: 2006


Oxford, 2006

In 2006, I had the privilege of attending two conferences in England (the 11th International Command & Control Research & Technology Symposium in Cambridge and the Complex Adaptive Systems and Interacting Agents Workshop in Oxford).

This was the year that NASA launched the New Horizons spaceprobe towards Pluto (it was to arrive in 2015). Ironically, later in 2006, the International Astronomical Union somewhat controversially downgraded the status of Pluto to that of a “dwarf planet.”

Grigori Perelman’s proof of the Poincaré conjecture was declared the “Breakthrough of the Year” by the journal Science. A variety of books, such as this one, have tried to explain what the conjecture (now theorem) is about. So far, this is the only one of the seven Millennium Prize Problems to be solved.

Perelman was offered, but refused, the prestigious Fields Medal (in interviews, he raised some ethical concerns regarding the mathematical community).

Books of 2006 included the intriguing World War Z (later made into a mediocre film). Movies included Pan’s Labyrinth, Children of Men, Apocalypto, Black Book, Pirates of the Caribbean II, Cars, and The Nativity Story.

And in music, Carrie Underwood took the world by storm, singing about Jesus and about smashing up motor vehicles with baseball bats.


Zero in Greek mathematics

I recently read The Nothing That Is: A Natural History of Zero by Robert M. Kaplan. Zero is an important concept in mathematics. But where did it come from?

The Babylonian zero

From around 2000 BC, the Babylonians used a positional number system with base 60. Initially a space was used to represent zero. Vertical wedges mean 1, and chevrons mean 10:

This number (which we can write as 2 ; 0 ; 13) means 2 × 3600 + 0 × 60 + 13 = 7213. Four thousand years later, we still use the same system when dealing with angles or with time: 2 hours, no minutes, and 13 seconds is 7213 seconds.

Later, the Babylonians introduced a variety of explicit symbols for zero. By 400 BC, a pair of angled wedges was used:

The Babylonian zero was never used at the end of a number. The Babylonians were happy to move the decimal point (actually, “sexagesimal point”) forwards and backwards to facilitate calculation. The number ½, for example, was treated the same as 30 (which is half of 60). In much the same way, 20th century users of the slide rule treated 50, 5, and 0.5 as the same number. What is 0.5 ÷ 20? The calculation is done as 5 ÷ 2 = 2.5. Only at the end do you think about where the decimal point should go (0.025).

Greek mathematics in words

Kaplan says about zero that “the Greeks had no word for it.” Is that true?

Much of Greek mathematics was done in words. For example, the famous Proposition 3 in the Measurement of a Circle (Κύκλου μέτρησις) by Archimedes reads:

Παντὸς κύκλου ἡ περίμετρος τῆς διαμέτρου τριπλασίων ἐστί, καὶ ἔτι ὑπερέχει ἐλάσσονι μὲν ἤ ἑβδόμῳ μέρει τῆς διαμέτρου, μείζονι δὲ ἢ δέκα ἑβδομηκοστομόνοις.

Phonetically, that is:

Pantos kuklou hē perimetros tēs diametrou triplasiōn esti, kai eti huperechei elassoni men ē hebdomō merei tēs diametrou, meizoni de ē deka hebdomēkostomonois.

Or, in English:

The perimeter of every circle is triple the diameter plus an amount less than one seventh of the diameter and greater than ten seventy-firsts.

In modern notation, we would express that far more briefly as 10/71 < π − 3 < 1/7 or 3.141 < π < 3.143.

The Greek words for zero were the two words for “nothing” – μηδέν (mēden) and οὐδέν (ouden). Around 100 AD, Nicomachus of Gerasa (Gerasa is now the city of Jerash, Jordan), wrote in his Introduction to Arithmetic (Book 2, VI, 3) that:

οὐδέν οὐδενί συντεθὲν … οὐδέν ποιεῖ (ouden oudeni suntethen … ouden poiei)

That is, zero (nothing) can be added:

nothing and nothing, added together, … make nothing

However, we cannot divide by zero. Aristotle, in Book 4, Lectio 12 of his Physics tells us that:

οὐδὲ τὸ μηδὲν πρὸς ἀριθμόν (oude to mēden pros arithmon)

That is, 1/0, 2/0, and so forth make no sense:

there is no ratio of zero (nothing) to a number

If we view arithmetic primarily as a game of multiplying, dividing, taking ratios, and finding prime factors, then poor old zero really does have to sit on the sidelines (in modern terms, zero is not part of a multiplicative group).

Greek calculation

For business calculations, surveying, numerical tables, and most other mathematical calculations (e.g. the proof of Archimedes’ Proposition 3), the Greeks used a non-positional decimal system, based on 24 letters and 3 obsolete letters. In its later form, this was as follows:

Units Tens Hundreds
α = 1 ι = 10 ρ = 100
β = 2 κ = 20 σ = 200
γ = 3 λ = 30 τ = 300
δ = 4 μ = 40 υ = 400
ε = 5 ν = 50 φ = 500
ϛ (stigma) = 6 ξ = 60 χ = 600
ζ = 7 ο = 70 ψ = 700
η = 8 π = 80 ω = 800
θ = 9 ϙ (koppa) = 90 ϡ (sampi) = 900

For users of R:

to.greek.digits <- function (v) { # v is a vector of numbers
  if (any(v < 1 | v > 999)) stop("Can only do Greek digits for 1..999")
  else {
    s <- intToUtf8(c(0x3b1:0x3b5,0x3db,0x3b6:0x3c0,0x3d9,0x3c1,0x3c3:0x3c9,0x3e1))
    greek <- strsplit(s, "", fixed=TRUE)[[1]]
    d <- function(i, power=1) { if (i == 0) "" else greek[i + (power - 1) * 9] }
    f <- function(x) { paste0(d(x %/% 100, 3), d((x %/% 10) %% 10, 2), d(x %% 10)) }
    sapply(v, f)
  }
}

For example, the “number of the beast” (666) as written in Byzantine manuscripts of the Bible is χξϛ (older manuscripts spell the number out in words: ἑξακόσιοι ἑξήκοντα ἕξ = hexakosioi hexēkonta hex).

This Greek system of numerals did not include zero – but then again, it was used in situations where zero was not needed.

Greek geometry

Most of Greek mathematics was geometric in nature, rather than based on calculation. For example, the famous Pythagorean Theorem tells us that the areas of two squares add up to give the area of a third.

In geometry, zero was represented as a line of zero length (i.e. a point) or as a rectangle of zero area (i.e. a line). This is implicit in Euclid’s first two definitions (σημεῖόν ἐστιν, οὗ μέρος οὐθέν = a point is that which has no part; γραμμὴ δὲ μῆκος ἀπλατές = a line is breadthless length).


In the Pythagorean Theorem, lines are multiplied by themselves to give areas, and the sum of the two smaller areas gives the third (image: Ntozis)

Graeco-Babylonian mathematics

In astronomy, the Greeks continued to use the Babylonian sexagesimal system (much as we do today, with our “degrees, minutes, and seconds”). Numbers were written using the alphabetic system described above, and at the time of Ptolemy, zero was written like this (appearing in numerous papyri from 100 AD onwards, with occasional variations):

For example, 7213 seconds would be β ō ιγ = 2 0 13 (for another example, see the image below). The circle here may be an abbreviation for οὐδέν = nothing (just as early Christian Easter calculations used N for Nulla to mean zero). The overbar is necessary to distinguish ō from ο = 70 (it also resembles the overbars used in sacred abbreviations).

This use of a circle to mean zero was passed on to the Arabs and to India, which means that our modern symbol 0 is, in fact, Graeco-Babylonian in origin (the contribution of Indian mathematicians such as Brahmagupta was not the introduction of zero, but the theory of negative numbers). I had not realised this before; from now on I will say ouden every time I read “zero.”


Part of a table from a French edition of Ptolemy’s Almagest of c. 150 AD. For the angles x = ½°, 1°, and 1½°, the table shows 120 sin(x/2). The (sexagesimal) values, in the columns headed ΕΥΘΕΙΩΝ, are ō λα κε = 0 31 25 = 0.5236, α β ν = 1 2 50 = 1.0472, and α λδ ιε = 1 34 15 = 1.5708. The columns on the right are an aid to interpolation. Notice that zero occurs six times.


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.