Mathematical Puzzles and Paradoxes

Mathematical Puzzles and Paradoxes

Professor Sarah Hart

30 January 2024

In this lecture we’ll going to look at riddles, puzzles and paradoxes, and how they can lead to some fascinating mathematical ideas and discoveries.

We humans are inherently playful and curious. In earlier Gresham geometry lectures, we’ve discussed things like boardgames, card games, and games of chance like dice. Games date back at least as far as archaeology can take us, and probably beyond. But there’s another way we like to entertain our minds that also goes back many thousands of years, and that’s what we are going to talk about today: puzzles and riddles. And specifically, written or spoken ones – I don’t mean puzzles like Sudoku or Rubik’s cubes. One of the lovely things about word problems like this is that you can see them spreading and evolving over time, rather like folk tales or fairy tales. You find variations of them in different countries, featuring different animals or people. Using plenty of examples, we’ll show how puzzles can tell us interesting things about both the history of mathematics and mathematics itself.  

The seventeen camels (and other stories)

Here’s one example: the seventeen camels.

The Sheikh died and left his herd of camels to be divided between his three sons. The eldest son should get half the camels, the next son a third of them, and the youngest one ninth. The problem was that the herd had 17 camels, so they got stuck with the division straight away. A passing traveller offered to help. “I shall lend you my camel”, he said. The herd now had 18 camels. So, the eldest son got half, which is 9, the next son got one third of 18, which is 6, and the youngest got one ninth, which is 2. That left just one camel, which the traveller jumped back on and rode away. What is going on?

The recreational mathematics expert David Singmaster researched the puzzle and found that problems involving these fractions, but without the entertaining camel story, date back at least 600 years, but problems with the same basic plot twist (which we’ll discuss in a moment) are even older than that – at least 3,500 years. The animals come on the scene later. By the 19th century we see this puzzle in English language books, but given an exotic flavour by being set in some unspecified Arab country with camels, or in China with elephants, in several putative locations with horses, cows or even, in one much more recent instance, Rolls Royces!  

Back to the camels: how do we resolve the confusing fact that an allocation that couldn’t be done with 17 camels can be done with 18, but the 18th camel isn’t actually used? It’s fairly simple if we look at it the right way. If you actually work out 12+13+19 , the answer is 1718 . So, the fractions don’t in fact add up to 1. This means that the will only disposes of 1718 ths of the camels, so it’s not possible to distribute the whole herd to the sons while meeting the exact terms of the will. What the solution does is to give each son a little more than that to which he is entitled: the first son should really receive 8.5 camels but gets 9, and so on. The underlying challenge here is what do to if you have to divide a quantity into a number of fractions that do not add up to 1. Problems relating to this, as David Singmaster found, date back at least as far as the Rhind Papyrus (circa 1650 BCE).

Following the evolution of a puzzle or type of puzzle over time (in this case a lineage of thousands of years) can give us fascinating glimpses of knowledge transfer between particular cultures at particular times, and as well as clues to the way that knowledge in general is transmitted, it hints in particular at how and when mathematical knowledge has spread from one place to another. If somewhere a puzzle appears that requires, in its solution, techniques to deal with, say, quadratic expressions, then that is good evidence that this knowledge itself is now available in that location. As an example of an ancient puzzle requiring just this, there’s a Babylonian tablet which asks the reader to find the length and width of a rectangle, given just the difference between them, and the area of the rectangle. With modern algebra we’d solve this quite quickly by writing down two equations, eliminating one variable, and ending up with a quadratic to solve. Although they did not have anything like the “quadratic formula”, the Babylonians did have an algorithm to solve problems like this one, which involves a specific type of quadratic expression.

One interesting phenomenon that can sometimes occur as problems spread is that the person appropriating them changes the wording without necessarily understanding the consequences. This can lead to problems that don’t have a solution, or incorrect solutions being given, or wrong explanations of why the solution is right. As an example, there is a whole class of problems of the following type (my version with “Monday” and “metres” is of course in modern language):

A snail is at the bottom of a well 2 metres deep. Starting on Monday it climbs half a metre each day but slips back 1/5th of a metre each night. What day will it get out of the well?

The first time you try a problem like this you probably say that the net climbs each 24 hour period is 12-15=310 m, or 30cm. So, it starts Tuesday morning 0.3m, then 0.6, 0.9, 1.2, 1.5, and on Sunday morning it will start at 1.8m, so it will get out sometime on Sunday. But this isn’t right. It starts Saturday at 1.5m, and so at sunset on Saturday it will reach 2m and escape just before nightfall. So, the answer is Saturday. I vividly remember getting a problem like this wrong myself as a child!

These kinds of puzzles seem to have originated in India at least 1500 years ago, when it was common to write complicated fractions like 310  in terms of simpler unit fractions. It’s been suggested that to begin with such puzzles simply said that the snail climbs “12-15 ” each day, meaning 310  each day. In that case, the subtlety about what happens at the end of this process is not required, and the correct answer really would be Sunday. But the puzzle migrated to what was then Persia, and eventually to Italy (why? Because of transmission of knowledge along trade routes), and in the process morphed into problems where the snail (or other animal – there are examples with snakes, dragons, even lions) first moves forward then goes back, at which point the different solution comes into play. But, interestingly, it seems to have taken at least a century for anyone to notice, so for a long while these later versions of the puzzle were given with the wrong solution. It finally seems to have been resolved in 14th century Italy.

Tracing the development and spread of knowledge is one fascinating aspect of investigating mathematical puzzles. In the next example we’re going to look at another benefit – mathematical ideas involved in the solutions can lead to deep and important mathematics.

Saving the day, the decanting way

Water jugs problems date back a long way and appear in many different guises. Here is an example:

You have a five-litre jug and a three litre jug, with no other markings on them. But you need to measure out exactly one litre of water. What can you do?

Puzzles in this spirit date back many centuries – another type is having (say) an 8L, 5L and 3L jug with the 8L jug full, and needing to split the 8L exactly into half. There are variants of both types with different numbers of jugs, different quantities, and different subdivisions required. We’ll just focus on the problem of two jugs, with volumes X  and Y , and you have to make 1 litre of water. I’ll call these (X,Y) -jug problems.

Beginning with the (5,3)-jug problem, the crucial thing to notice is that if we could find some combination of fives and threes that makes 1, we’d be happy. For instance, 2×3-1×5=1 . This gives us a solution: we repeatedly fill the 3L jug and repeatedly pour the contents into the 5L jug (emptying that jug whenever it is completely filled), then after two fillings of the 3L jug and one emptying of the 5L jug, we’ll have 1L of water left in the 3L jug.

Similarly, let’s say we have a 7L and a 5L jug. This time, 3×5- 2×7=1 . So, we can repeatedly fill the 5L jug, pour the contents into the 7L jug, emptying as required, and after three fillings of the 5L jug and two emptyings of the 7L jug, we’ll have our 1L of water.

Finding a solution to any such jug problem is in fact equivalent to finding an expression aU - bV = 1 , where U  and V  are the volumes, in some order, and a  and b  are integers. One thing this tells us is that if the volumes have any common divisor bigger than 1, we are in trouble, because if that were so then the left-hand side would be divisible by that factor, but the right-hand side would not. So, we only have a chance if our two volumes, like 3 and 5 or 5 and 7, are coprime, in other words their greatest common divisor, or gcd, is 1. There’s a very cool technique called the Euclidean algorithm for finding the gcd of two numbers, to check this, but it also provides us with a way to solve any water jugs problem of this kind! I’ll show you an example.

Let’s suppose our two jugs are 35 and 11 litres and we want to find their gcd. (These numbers are small enough that we can instantly tell their gcd is 1, but for larger numbers it’s much less obvious.) The process is simple. First, divide 35 by 11; we get 3 remainder 2. That is,

35=3×11+2.

Anything that divides both 11 and 2 must divide 35, so is a common divisor of 11 and 35. But also, because 2=35-3×11 , anything that divides both 11 and 35 must also divide 2, so is a common divisor of 11 and 2. So gcd(35,11) = gcd(11,2). Now we go again with 11 and 2.

11=5×2+1.

By the same reasoning, gcd(11,2) = gcd(2,1), but that’s just 1. So gcd(35,11) = 1, as we thought. However, we can now do some magic with these two equations. Rewriting the second one we have

1=11-5×2 . And from the first one, 2=35-3×11 . So, we can substitute:

1=11-5×35-3×11=16×11-5×35 . This means we can solve the (35,11)-jug problem by filling the 11L jug sixteen times and pouring it into, and emptying, the 35L jug five times. The Euclidean algorithm gives us a way to solve every valid (X, Y) -jug problem (by valid, I mean that a solution exists, which occurs, as we’ve said, exactly when gcd(X,Y) = 1 ). Bruce Willis solved the (5,3)-jug problem in the action film Die Hard 3, to stop a bomb set by a malevolent terrorist. He clearly knows the Euclidean algorithm!

The Euclidean algorithm is not just useful for defusing fictional bombs. It has an important role in cryptography. I don’t have time to go into all the details but it’s a vital component of the RSA encryption algorithm that is the basis of much online encryption. Essentially, to decrypt you need to use the Euclidean algorithm on two numbers, call them K  and X , to find a  and b  such that aK+bX = 1 . That number a  is the thing that allows you to decrypt the message. The number K  is the “public key”, it’s publicly available. But the number X  is secret. Without it you can’t find the decryption key a , except by brute force attack. If you use large enough numbers RSA is therefore essentially impossible to crack.

Crossing bridges to the real world

The water jugs problem relates to some nice mathematics, but that mathematics wasn’t devised specifically to solve the problem. So why bother with the puzzle? Is this “recreational mathematics” worthwhile? Of course, for a mathematician, the phrase “recreational mathematics” is a tautology. Play is worthwhile in and of itself. Interesting puzzles are also a great invitation to the wonders of mathematics. (The following tongue-in-cheek caution appeared on the cover of one book by renowned popular mathematics writer and hero of recreational mathematics. WARNING: Martin Gardner has turned hundreds of innocent youngsters into math professors and hundreds of math professors into innocent youngsters.) But there can be unexpected consequences in terms of new mathematics that has useful real-world applications. The most famous example of this is the Bridges of Königsberg problem. The town of Königsberg had seven bridges, and the puzzle was whether it is possible to go for a walk around the town that crosses each bridge exactly once. The great mathematician Leonhard Euler proved that it was impossible. In doing so he created a whole new field of mathematics – graph theory – that studies the properties of networks of vertices and edges (or lines and nodes). The mathematical properties of networks have applications in everything from transport connections to the internet. One example from the world of word problems of puzzles whose solutions involve highly applicable mathematics comes from “buying birds” problems – first seen in 5th century China, but here’s an example from Fibonacci’s early 13th century book Liber Abaci: “The three kinds of birds”. You are told that thirty birds are bought for a total of thirty pence (or denarii, in the original). There are three kinds of bird: partridges, pigeons, and sparrows. Partridge cost 3 pence, pigeons 2, and sparrows are two for a penny. What are the possibilities for how many birds of each kind are bought? (For a fuller discussion of this problem, as well as how Fibonacci solved it, see my Gresham lecture The maths of coins and currencies.) The study of problems like this has developed into a subject known as linear programming, or linear optimization, which today has applications in everything from transport to manufacturing. For manufacturing, you might want to optimise your profits by knowing what quantities of each different variety of product to make, with each variety costing a different amount of time and/or money to produce, and being sold for a different amount. In transport, it might be working out the best way to deploy your transport fleet (single decker buses, double decker buses, etc) to get a given number of people to a given number of destinations in the most efficient way.

Helping Achilles beat the tortoise

A particularly fun class of puzzles are those which present a seemingly impossible situation – a paradox which we are challenged to resolve. In the “seventeen camels” puzzle, the apparent paradox can be resolved when we realise that the fractions do not add to 1: it’s an object lesson in the value of clear thinking. But sometimes a paradox requires much more than this, and addressing it forces us to think deeply about words and concepts, and sometimes even to develop new mathematics. That’s what we’ll think about for the rest of this talk.

Zeno’s paradoxes are probably the most famous ancient paradoxes, and it wasn’t possible to resolve many of them fully until mathematics developed entirely new techniques many centuries later. Achilles and the Tortoise is the paradox that if Achilles is, say, 100 metres away from a tortoise that’s moving very slowly, then even though Achilles runs very fast, he can never catch up to the tortoise because by the time he covers those 100 metres, the tortoise will have moved a little way further, and by the time he makes up that small distance the tortoise will have moved on again, so he can never catch it. A related paradox says that though Atalanta is a very fast runner, she can in fact never get anywhere at all, because to get from A to B she has to first cover half the distance, and then half the remaining distance, and so on, so she has an infinite number of distances to travel, which is impossible. Both of these paradoxes boil down to summing an infinite series, which is notoriously problematic (how do we know what the outcome of adding infinitely many numbers together will be – our intuition is rather poor in such situations), but the underlying issue is that we are trying to describe a continuous process – motion – in terms of discrete events. Even more stark is the paradox of the arrow. An arrow flying through the air, if we do a freeze frame, is at rest. So, its movement is made up of infinitely many instants of time in which the distance it moves is zero. How does it get anywhere? Calculus, which was developed by Isaac Newton and Gottfried Leibniz (let’s not get into who thought of it first!) is the tool we need to understand continuous processes in a mathematically rigorous way.

Beard-scratching logic

Paradoxes of logic also have a venerable history. The philosopher Epimenides of Knossos famously said “All Cretans are liars”. The problem is that since Knossos is in Crete, that makes Epimenides a Cretan himself. If the statement is true, then Epimenides is himself a liar, so the statement, because he made it, is a lie. There isn’t a logical contradiction, though, if the statement is false. That would mean not all Cretans are liars, but Epimenides could still be one of the dishonest ones. (See also the exam papers that say “this page is left intentionally blank”.) However, what are we to make of a sentence that asserts “this sentence is false”? If it’s true then it’s false, and vice versa. Which is it? We could say it’s both true and false. I don’t like that view, because these seem like contradictory claims: we usually consider it a basic tenet of logic that something can’t be both true and false at the same time. Another approach is to say that it’s neither true nor false (because either assumption leads to a contradiction). I quite like the following argument which has been attributed to the logician Arthur Prior: every sentence implicitly asserts its own truth. “The sky is blue” is a claim that the sky is indeed blue. So, it’s logically equivalent to “The sky is blue and this sentence is true”. With this in mind, “this sentence is false” is equivalent to “this sentence is false AND it is true”, which is impossible. Therefore, the sentence is false. Whatever interpretation we prefer here, thinking about it is very useful to get some clarity around the ground rules of logic.

Since I love mathematical references in literature, I can’t resist sharing one more paradox, which was put to Don Quixote’s faithful servant Sancho Panza in Cervantes’ novel. You are the magistrate in a town with a curious rule. All travellers crossing the bridge to the town must state what they will do there. If they tell the truth, then they are free to go. If they lie, then they will be hanged. One day a traveller, when questioned, says “I will be hanged”. What should you do? If you hang him, then you make his statement true, which means he should have been allowed to go free. But if you don’t hang him, then that means he lied, for which he should be hanged! It seems like every choice is wrong. If you want to know Sancho Panza’s most excellent verdict, you’ll have to read the book!

Now try this one, which I believe is due to Martin Gardner: “This sentence has seven words”. Clearly false. If a statement is false, then its negation is true. Unfortunately, “This sentence does not have seven words”, is also false. Help! The problem here, and with “this sentence is false”-type statements – broadly known as “liar paradoxes” – is that they are self-referential. The way out of “this sentence has seven words” is to notice that although it is self-referential, it doesn’t necessarily follow that its negation is. We need to move up a layer and distinguish the statements from the statements about the statements – the language from the metalanguage, if you will. If Sentence A is “This sentence has seven words”, then the actual negation, which I’ll label Sentence B, is: “Sentence A does not have seven words”. This time, Sentence A is false and Sentence B is true. So, all is well.   

But sometimes the problem goes deeper than getting our heads clear about semantics. Genuinely self-referential statements can cause serious challenges, and even threaten the foundations of mathematics. The so-called barber paradox is a case in point.

In a certain town, fashion dictates that all the men be clean-shaven. The town has a single barber. He shaves only those men who don’t shave themselves.

Fair enough. Except: who shaves the barber? Suppose he shaves himself. But the barber only shaves men who don’t shave themselves. So, he cannot shave himself. On the other hand, if he doesn’t shave himself, then he’s one of the people who the barber does shave. So, he does shave himself.

One can resolve this quite easily by saying that clearly such a town cannot exist. But the paradox was designed to draw attention to a genuine mathematical problem.

Shaking the foundations

In the late 19th and early 20th century, huge efforts were being made to put the whole of mathematics on a rock-solid logical foundation, breaking down the subject into its most fundamental building blocks, axioms and rules of logical inference, so that in theory starting just from those axioms, and applying step-by-step reasoning, without having to force the reader to take on trust any intuitive leaps, one could build up an impregnable fortress of pure logic (or something like that!) that covers everything. A basic principle of any proposed system would be things you can prove in that system must be true, that nothing can be both true and false at the same time, and that therefore it must be impossible to prove a false statement (known as a contradiction). A short way of saying this is that the system must be consistent – you can prove at most one of a statement and its negation.

For instance, think about sets. You can have sets and combine them to make new ones, by taking things like the intersection, union, complement (everything not in the set), and so on. You can define sets by looking at subsets with particular properties. So, we might look at the set of all rectangles, and then the subset whose length and width are equal (which gives the squares). Or we might look at the set of all prime numbers, and define a slightly self-referential subset, those primes p  for which 2p+1  is also prime. We end up with the Sophie Germain primes. You can think about sets of anything, even sets of sets. One thing we find useful to study, for instance, is the set of all subsets of a given set – this is called the power set. If we are studying the properties of sets in general, how we can manipulate them and define them and so on, this is called set theory. Mathematicians were trying to codify all this at the end of the 19th and start of the 20th century, setting up rules of engagement, like if A and B are sets, then the union of A and B is a set, and the set of all subsets of A is a set, and the set of all elements of A that satisfy a particular criterion is a set, and so on. One of these mathematicians, Gottlob Frege, had in 1903 just completed Volume 2 of an epic work called Foundations of Arithmetic, aiming to build up laws of numbers and sets, when Bertrand Russell wrote to him pointing out that in his system, something like the barber paradox could occur.

If you can have any set, and you allow sets of sets, you can define the set of all sets – this set would contain itself as an element, which is not necessarily an issue, though it’s a bit of a strange Russian doll concept. However, consider the set S of all sets that do not contain themselves. If S contains itself, then by definition S does not contain itself. But if S does not contain itself, then it qualifies as a member of S. So S is neither in S or outside S, which is impossible. This set S cannot exist. But within Frege’s set-up, it (or something tantamount to it), could be defined. So, the whole system is inconsistent and cannot work. Poor Frege added an appendix to his book, saying “Hardly anything more unfortunate can befall a scientific writer than to have one of the foundations of his edifice shaken after the work is finished. This was the position I was placed in by a letter of Mr Bertrand Russell, just when the printing of this volume was nearing its completion”.

In fact, it would turn out that the whole project of finding an all-encompassing system of logic, that could deal with all of mathematics, is doomed. Such a system would consist of a set of axioms, along with some rules of inference that allow further statements to be deduced. The ideal is to find such a system covering the whole of mathematics which is both consistent and complete. “Consistent” means there are no contradictions in the system: false statements cannot be derived from the axioms.  “Complete” means that every true statement that can be made within the system can be proved within the system, starting from the axioms and only using the allowed rules of inference). Combined, it means every statement we can make within the system is either true or false (not both), and we can prove it in the system if and only if it is true. Kurt Gödel famously showed (Gödel’s Incompleteness Theorem) that this is impossible, even if we restrict our attention only to mathematical properties of the natural numbers. The full argument is highly technical, but in essence he showed that if a system is sufficiently complex to contain all the kinds of statements we’d need, then it is possible to make a statement in the system that says, in essence, “This statement cannot be proved within the system”. Now, if the statement is false, then it can be proved within the system. But the system is supposed to be consistent, which means only true statements can be proved. So, the statement can’t be false. Therefore, the statement is true. But that means it cannot be proved within the system. The upshot is that we have a statement we know is true, but our system cannot prove it! This doesn’t mean mathematics is broken, but it does mean that there’s no hope of a dystopian future where the whole of mathematics can be completed by putting some axioms in a logic machine and cranking the handle until the proof or refutation of the Riemann Hypothesis (and every other conjecture) falls out. With this good news for the ongoing employment prospects of mathematicians, it seems a good place to finish.  

© Professor Sarah Hart 2024

References and Further Reading

• If you enjoy thinking about mathematical puzzles, you will be delighted by literally anything written by Martin Gardner. He inspired generations of mathematicians and puzzle enthusiasts, and regular events are held in his honour by the G4G (Gathering 4 Gardner) community. On the 21st of each month in the last couple of years, G4G has been hosting a virtual “Celebration of Mind” and everyone who loves mathematics, puzzles, literature, skepticism, and magic of all types is invited to join. https://www.gathering4gardner.org/
• Similarly, anything written by David Singmaster is sure to enchant. If you are interested in the history of recreational mathematics I strongly recommend his two-volume Adventures in Recreational Mathematics (World Scientific, 2022). Not only does it describe hundreds of puzzles, their origins and solutions, but it also has an extensive bibliography of historical sources and hundreds of references if you want to dig deeper, so it’s an indispensable starting point.
• The British Society for the History of Mathematics has regular events and is planning a recreational mathematics conference in late 2024. If you join the society, you get access to the entire archive of its journal, which has regular articles on the history of recreational mathematics, including several by David Singmaster. https://www.bshm.ac.uk/
• They’re of a mature vintage nowadays but for my money you can’t beat Raymond Smullyan’s books of logic conundrums – the liar paradox is just the start! Any one of these will give you days of enjoyable paradoxical puzzling: What Is the Name of This Book? (1978); This Book Needs No Title (1980); To Mock a Mockingbird (1985); and Forever Undecided (1987).
• I mentioned that other kinds of games and puzzles had been discussed in some of my earlier Gresham lectures. These are as follows.
  • The maths of Sudoku & Latin squares: https://www.gresham.ac.uk/watch-now/maths-sudoku
  • The maths of board games: https://www.gresham.ac.uk/watch-now/maths-games
  • Lottery-winning maths: https://www.gresham.ac.uk/watch-now/lottery-maths
  • The maths of coins and currencies (for the Fibonacci “thirty birds” problem https://www.gresham.ac.uk/watch-now/maths-coins)  

A note on images used in the lecture

To the best of my knowledge all the images used are either in the public domain, or may be used for educational purposes under fair use rules, or were created by me.

© Professor Sarah Hart 2024