“The Raven’s Hat” by Jonas Peters and Nicolai Meinshausen
All rights reserved.
This book introduces, with some variations, eight mathematically flavoured games or puzzles. As the authors accurately explain in their preface, the type of problems they present look at first sight almost impossible to solve. It is only after a careful analysis, reducing it to a formal (say mathematical) reformulation, that it becomes clear that a solution strategy can be designed that is in some sense even optimal. Each time, the discussion of the solution to a problem is taken as an excellent pretext to explain some piece of mathematics. A reader with a minimal mathematical background will learn what a Hamming code is, what a cyclic group is, and some elements of linear algebra, probability, and even broader topics such as information theory, projective geometry, and algebraic topology. What starts as a playful game with a seemingly impossible solution becomes, after placing it in an appropriate mathematical context, relatively easy to solve. Moreover, by isolation and abstraction of the essentials, it becomes simple to consider more general situations. A better advertisement for the power of mathematics and a stronger motivation to study mathematical formalism and mathematical structures can hardly be found.
The book opens with a classic game, which is also for the title of the book. So let’s take this as an illustration of the concept used by the authors throughout. Consider three players (in this book the players are adorable ravens illustrated in graphics by Malte Meinhausen). Each player has a blue or red hat on his head. They see the other players but they cannot see the colour of their own hat. All players have to guess their own hat’s colour (red, blue, or don’t know) without communicating with each other. The players, as a team, win the game if at least one player is correct and none is wrong (where the don’t know answer is not considered wrong). There exist innumerable variations of this type of game, generally called ”hat-problems”. The present problem, which asks for a successful collective strategy, was originally formulated by Todd Ebert in 1998. It was Elwyn Berlekamp who later connected the solution to coding theory and solved it for players when is of the form . The solution for general is still an open problem today. This kind of (brief) historical background of the problem is also given for the problems presented in the other chapters, which is a nice feature of the book. To work towards solving the problem, the authors first propose some guessing strategies or naive trials, possibly introducing a first formalism such as coding the red-blue colours as 0-1 and the configurations of three hats as binary numbers from 000 to 111, with the first bit for player 1, the second for player 2, and the last for player 3. This shows that there are a total of 8 possible states, and each player knows 2 of the 3 bits in the true number and must guess the bit of her own position. The probability of winning for the 3 players is maximized if each player chooses her own colour (0-1 bit) so that the ”distance” to one of the possibilities is minimal. The crux is to define this distance as the Hamming distance, which is the mathematical contribution to the solution in the form of coding theory. Once the principle is clear, it is easy to generalize the solution to players.
This problem involves some elementary probability, and probability is also an ingredient for several of the other problems discussed in this book (both of its authors are professors of statistics). Several variants of the game correspond to the following description: a set of players needs to guess something on the basis of partial information that is available to them, and the goal is to agree on a strategy that will maximize their chance of winning the game as a team. For example, in the second game of this book, the players have their name hidden in boxes, and they have to find the box with their own name in a minimal number of trials for the whole team. Here the mathematical tool is the factorization of a permutation into cycles. In the existing literature, the players are often presented as prisoners that are collectively freed if they win. In this book, the stories vary, but all the illustrations portray ravens with hats.
Let me skim more quickly over the other chapters. Somewhat related to the two hat-problems mentioned above is a problem where there are more colours for the hats and where the players are lined up in such a way that each player can only see the other players (and their hats) who are positioned in front of them. This seems to contain strictly less information than when they can all see each other, but when the players start guessing the colour of their own hat one after another, starting with the one at the back, the extra information is provided. Here it is cyclic groups that come to the rescue to solve the problem. Another game is a magical card trick which is based on understanding correctly how much randomness is introduced in an ordered card deck by riffle shuffling or cutting the deck. While the previous problems involved simple counting, a bit of probability, and basic algebraic concepts, there is no way around introducing the logarithm when information theory is involved. Not that the logarithm is an advanced topic, but still it requires some understanding of mathematics beyond counting. A further game introduces some projective geometry with a pinch of graph theory. Somewhat of a different nature is the problem involving two globes placed randomly on the table, in which one is asked to find the place or country that are in the same (or opposite) position on the two globes. This means that the axis defined by the position of that place on globe 1 and the globe centre should be parallel to the corresponding axis for globe 2. For this problem, one needs to realize that there is a mathematical one-to-one match of the two globes by a translation (to match up the centres) and a single rotation. The axis of the latter gives the solution. This requires the introduction of some linear algebra to see that the problem is a simple eigenvalue problem for a 3D rotation matrix. The final game is, once again, a classic, involving hanging a picture on a wall. If there is one nail on which the frame string can be hooked, then the picture will fall when the nail is removed. The game is to wind the string of the frame around two (or more) nails in such a way that if one nail is removed, the frame will not drop to the floor. Here the naive reader is confronted with group theory and algebraic topology to find a general solution.
For an inexperienced puzzler, the problems look challenging at first sight, so she is gradually guided by the authors towards a solution with several variants of naive trials, pointing at the shortcomings, and just enough mathematics is used to deal with the problem at hand. If, in a top-down approach, the mathematics were to be introduced first with the problem solution as an a posteriori application, this approach would not have the same motivating effect. A simple problem that has a hard solution leads to mathematics that not only solves the original problem, but that can immediately be applied to generalizations and other variants of the problem. For readers who are attracted to solving puzzles and games, but who have a weak (or no) mathematical background, the authors provide several appendices with additional explanation of notation, binary and complex numbers, converging sequences, probability, etc. as well as some extra details on specific problems discussed in the chapters. This is an engaging book that all puzzlers, and certainly novices to the field, will love.
MIT Press, 2021, 192 pages, Paperback ISBN 978-0-262-04451-6
“Games for Your Mind” by Jason Rosenhouse
All rights reserved.
If you ask a connoisseur where to look for logic puzzles, then she will almost certainly mention Raymond Smullyan (1919–2017), and perhaps also Lewis Carroll (1832–1898) and some of the columns of Martin Gardner (1914–2010). Obviously, this kind of puzzle has existed since antiquity, but these three names are certainly among those that popularized the topic as we know it today. Jason Rosenhouse is a mathematics professor at James Madison University. He has written a book on the The Monty Hall Problem (Oxford, 2009), he is also the co-author of one entitled Taking Sudoku Seriously (Oxford, 2011), and he is a co-editor of three volumes on Mathematics of Various Entertaining Subjects (Princeton, 2015–2019); with all this, he has gained quite a reputation in the gamers-and-puzzlers community. This book will considerably add to his authority.
In his preface, Rosenhouse mentions that his original idea was to write a book with some entertaining logic puzzles à la Carroll and Smullyan. However, the actual result is a book that goes well beyond a mere collection of entertaining brain teasers. It explains the mechanisms and principles needed to solve the puzzles, but it also instructs the reader about the history of logic and its interpretation by different philosophical disciplines. Some example puzzles are solved and discussed, and just as in a mathematics textbook, some solved exercises are inserted to illustrate the theory. After each principle is explained, a list of puzzles is given for the reader to solve. They feel like exercises after the lesson; solutions are given at the end of each chapter.
It is clear that logic influences and interacts with mathematics. Deciding what is true and what is not, means deciding what to accept as being proved or not. This is done by checking the rules that were followed to arrive at the result. Therefore, one has to agree on what rules should be followed and what axioms one should start from. This quickly results in a discussion about the foundations of mathematics and philosophical considerations. Thus, while the puzzles as such are challenging but entertaining, it is also necessary to assimilate some background for which a leisurely scanning of the text is insufficient; it really requires staying focused while reading.
Rosenhouse divides the book into five parts: (1) A general introduction to logic and puzzles, (2) Lewis Carroll and Aristotelian logic, (3) Raymond Smullyan and mathematical logic, (4) Puzzles based on nonclassical logics, (5) Miscellaneous topics. The titles of the first four are self-explanatory. First, in part one, some general considerations about logic are given as well as some sample puzzles to whet the appetite. Logic is boringly simple in everyday life, but when philosophy is involved, it needs more precise definitions of its atoms, called propositions, and one must understand the mechanism of categorical syllogisms if one wants to explore puzzles based on Aristotelian logic.
Parts 2 and 3 are the main parts of the book. In the part about Lewis Carroll, a short introduction of Aristotle’s syllogism serves as an introduction to a discussion of Carroll’s book The game of logic (1886), in which he used certain diagrams to visualize the syllogism that solves the puzzles. In his book Symbolic logic (1896), Carroll solves sorites puzzles, meaning that one must deduce a conclusion from more than two categorical propositions. Rosenhouse explains how Carroll did this with more analytical techniques and tree graphs. Finally, the book discusses two journal papers that Carroll published in Mind. The first one involves if-then propositions and modus ponens and modus tollens arguments. The other paper is a regression problem. If and are true, then one would normally conclude that is true, using . But what if we do not accept the latter form of the modus ponens? A naive solution is to add it to the system, but that sets into action a recursive addition of propositions ad infinitum like in Zeno’s paradox of Achilles and the tortoise. Rosenhouse gives an extensive discussion about how this problem has been tackled by different authors.
In part 3, we leave syllogisms and move on to newer forms of formal logic, with Smullyan as the main puzzler. Smullyan’s puzzles often involve knights (who always speak the truth) and knaves (who always lie). Some examples of this type of puzzle are given with a bit of formal logic in an appetizing chapter. This is however then followed by several chapters on the history of logic, ranging from Aristotle through John Locke, George Boole and John Venn, to the formal system of Bertrand Russell and Kurt Gödel’s incompleteness theorems. There is less room for puzzles in these chapters; however, some elements can still be illustrated in puzzle form, typically the Smullyan type puzzles in which we meet people who may be either knights or knaves. In this type of problem, one usually is tasked with asking a question which reveals either who is what or what is true. In several puzzles where the problem is to find out whether is true, the appropriate question to ask has the form: Is true if and only if you are a knight? Smullyan attributes this principle to Nelson Goodman.
Part 4 gives an introduction to several more recent forms of logic. For example, three-valued logic is involved if people can be knights, knaves or neutral. Or probability can be involved in fuzzy logic if people are not either knights or knaves, but can be picked from a continuum between the two extremes, so that they answer questions truthfully or not according to a certain probability distribution.
Finally in the last part, several further topics are discussed. One is the Hardest Logic Puzzle Ever published by George Boolos in 1996, which has attracted a lot of academic interest, becoming a bit of a legend with a life of its own. This puzzle involves three gods: one answers with a lie, one with the truth, and one answers randomly. You do not know who is who and their answers are “da” and “ja”, but you do not know which word means “yes” and which one means “no”. The problem is to find out how many questions you need to ask, and which ones, in order to discover who is who. Other topics in this part are paradoxes and so called metapuzzles (in which some extra hidden information can be deduced). The concluding chapter gives some examples from fiction in the form of film and literature where some logic is involved. It ranges over a broad spectrum from Mr. Spock in Star Trek to the famous super-intelligent detectives Auguste Dupin, Sherlock Holmes, Hercule Poirot, and many others who solve crimes using logic. An appendix contains a very useful glossary of definitions of logic-related terms, along with an extensive index.
Even though this book is entertaining and addressed to a lay public, it goes well beyond a mere popularizing puzzle book, situated somewhere between entertainment and an introductory course in logic. The part on Gödel’s theorems is, for example, not just entertaining but quite a good explanation of the problem for an interested lay reader, including a Turing-like machine. The puzzles presented range from simple to extremely difficult. In most cases, the origin of the puzzle is mentioned. They are usually formulated as stories, in imitation of the initiator of the genre, Lewis Carroll, who always formulated his puzzles for children. Lovers of the Smullyan puzzles or Lewis Carroll will be happy to read the background material compiled in this book. Conversely, it may also introduce readers to Smullyan’s many puzzle books. Moreover, extending the type of underlying logic, Rosenhouse opens a door to more general types of entertaining puzzles. To raise interest in logic is a good thing not only for everyday life or for mathematics, but also for computer science, where it plays in important role in topics such as logic programming and its use in machine learning.
Princeton University Press, 2020, 352 pages, Hardcover ISBN 978-0-691-17407-5, e-book ISBN 978-0-691-20034-7