Algorithmic Puzzles

Anany Levitin and Maria Levitin
OXFORD UNIVERSITY PRESS USA 2011, 336 PAGES
PRICE £13.99 (PAPERBACK) ISBN 978-0-199-74044-4

This book is a collection of one hundred and fifty puzzles that can be solved by using clearly defined algorithmic procedures. The authors state that solving algorithmic puzzles is the most productive and definitely the most enjoyable way to develop one’s algorithmic thinking skills. If I had any doubts about this before I started working my way through this book I assure you that they are now completely gone.

Writing about a book filled to the brim with puzzles, I feel I have to describe a couple of my favourites.

Puzzle No. 21 Square Dissection
A square can always be divided up into an exact number of smaller squares, apart from the cases of 2, 3 or 5 squares.

Here are some examples of a square being divided into 4, 7 and 8 squares.
 

The reason that 2, 3 and 5 are not possible is due to the fact that the four right angles of the initial square must be in the smaller squares and this cannot happen in the three special cases of 2, 3 and 5.

Puzzle No. 97 The Game of Topswops
Invented by John Conway this game is traditionally played with the thirteen cards of the same suit.
 

© Mark Eaton | Dreamstime.com


If you start with five cards, ace to five, from a deck you see clearly how the mechanics of the game works. Shuffle the cards and place them face up so you can see the top card. Use the value on the uppermost card and count that many cards onto the table, then put these cards back on top of the deck. For example, if the deck was ordered from the top 32514 you would count three cards onto the table and then put these cards back on top to get the new order 52314. You now repeat this procedure with the new top card, 5 in this case, to get 41325. The game ends if an ace appears on top, as this results in a one-loop pattern.

You can play this game with more or less cards and also against other players to look for patterns. In a game of two or more people, each player shuffles their set of cards. The first player calls their top card and the second player counts off that number from their pack and then replaces these cards on top of their deck. The second player then calls their top number for the first player. The winner is the first player to get an ace as their top card.

An interesting question to consider is where does the ace have to be placed in the deck to give the greatest number of turns before it appears at the top of the pile?

The book is divided into three main sections – puzzles, hints, and solutions. I highly recommend this book as an engaging ‘pencil and paper’ read.

Steve Humble FIMA
Book review published directly onto the IMA website (April 2013)
 

How to Fold It: The Mathematics of Linkages, Origami and Polyhedra

Joseph O’Rourke
CAMBRIDGE UNIVERSITY PRESS 2011, 190 PAGES
PRICE £19.99 (PAPERBACK) ISBN 978-0-521-14547-3

This book is a triptych, unsurprisingly consisting of parts on linkages, origami and polyhedra.

Linkages, such as those found in a desk-lamp, or those which turn linear motion into rotary motion in order to move a car, are covered in the first three chapters. Ideas about the range of motion available to a robotic arm are covered through the use of vectors and elementary geometry. The book is stuffed full of colour diagrams and illustrations, which aid comprehension and really help bring the text to life.

The second part is on the more familiar subject of origami. This starts by formalising the treatment of the so-called ‘mountain’ and ‘valley’ folds, and then moves onto bigger questions, such as whether it is possible to fold a map flat, conforming to a given crease pattern. The second part then builds to the central result known as the fold and one-cut theorem, which states that any straight-line drawing on a sheet of paper may be folded flat in such a way that one straight scissors cut completely through the folding cuts all the segments of the drawing and nothing else. We have all cut out paper people from a folded piece of paper, with the intention that they end up linked at the hands, however I certainly found it surprising that this could be generalised to any line drawing, requiring no symmetry whatsoever.

The final part of the book is on polyhedra, which explores the folding and unfolding of the surface of a polyhedron. A net for a cube is elementary, one for a truncated icosahedron (football) can be found with a little work, but does every polyhedron have a net? With some thought it is not too difficult to find an example of a non-convex polyhedron that has no net, and one is given in the book. However, the case of convex polyhedra is still an open problem. The rest of this part is dedicated to nets of orthogonal polyhedra (think stacks of Lego bricks).

After providing a fast-paced introduction to the subject matters under discussion, a final section entitled ‘Above & Beyond’ is included in each chapter. These consist of more advanced material designed to make the reader really think, as well as some open problems. These sections can be skipped over on a first reading without detracting from the reader’s overall enjoyment of the book. Some of the open problems posed are, like so many open problems in combinatorics, so simple to state, and could possibly yield an elementary solution, given the right approach, which makes them all the more tantalising.

Each chapter is littered with graded problems - from those that help consolidate what has just been read, to those that present the reader with something meatier. Full solutions are provided for all the exercises.

The website accompanying the book provides a wealth of resources, such as templates to illustrate some of the ‘fold and one-cut’ examples, such as a turtle, as well as videos which help to visualise some unfolding orthogonal polyhedra. It also includes updates on the open problems posed in the book, such as the flattening polyhedra problem: Can every polyhedron be creased and then continuously flattened? This problem has now been solved, and the answer is yes.

This is a fun book and has minimal prerequisites, so really is suitable for anyone with an interest in the subject matters.

George Matthews AMIMA
Book review published directly onto IMA website (April 2013)

Mathematics of Life: Unlocking the Secrets of Existence

Ian Stewart
PROFILE BOOKS 2011, 368 PAGES
PRICE £20.00 (HARDBACK) ISBN 978-1-846-68198-1

‘Biology will be the great mathematical frontier of the twenty-first century.’ So says Ian Stewart, Emeritus Professor of Mathematics at Warwick University (and undoubtedly well known to all readers of this magazine). In the Mathematics of Life he suggests that, historically, there have been five revolutions that have changed the way scientists think about life and that a sixth – the mathematical solution of biological problems – is on its way.

The early chapters concentrate on the first five revolutions: the microscope; the Linnaeus classification system; the theory of evolution; genetics and the structure of DNA. These concentrate on the biology, which he explains very clearly, but, of course, he throws in some mathematics and historical sketches of the people involved as well.

Perhaps because the author is a mathematician not a biologist, he takes great care to explain the biology carefully, assuming the reader is basically ignorant of the field (certainly a correct assumption in my case!). So, for example, not only does he describe, say, the difference between prokaryotes and eukaryotes in terms of their structure, but he also gives examples: bacteria are prokaryotes; amoebas and tigers are eukaryotes. I found his explanation of genetic inheritance, in his discussion of Mendel’s experiments in the chapter called ‘In a Monastery Garden’, particularly enlightening.

When talking of genetics he emphasises the fact that, though DNA may be seen as a ‘blueprint’ for life, you need much more than a blueprint of something to understand how to make it or to predict all of its capabilities. This is especially true of biological systems.

The book contains several snippets of the ‘not a lot of people know that’ kind. For example, did you know that DNA was first discovered by Friedrich Miescher, a Swiss doctor, when analysing pus in bandages that had been discarded after use in surgery? Also, slime mould placed on a map of the area around Tokyo, with food sources placed at the locations of 36 cities, managed to produce a network of tubes connecting the food sources that closely matched the actual rail network connecting those cities! And the structure of certain viruses are best modelled using four-dimensional geometry (the author quotes the work of Reidun Twarock, which also forms the basis of one of the IMA’s Mathematics Matters articles, Fighting Infections with Symmetry, which was reproduced in the April 2011 issue of Mathematics Today and is also available on the IMA website.

Professor Stewart provides several thought-provoking discussions on a range of topics from genetically modified foods to alien life-forms and what we mean by the word ‘life’ itself. He has strangely little to say explicitly about his sixth revolution, but he does note: ‘I doubt that mathematics will ever dominate biological thinking in the way it now does for physics, but its role is becoming essential’, and ‘By the time we get to the twenty-second century mathematics and biology will have changed each other out of all recognition, just as mathematics and physics did in the nineteenth and twentieth centuries.’

The book is a fascinating read and I highly recommend it.

Alan Stevens CMath FIMA
Book review published directly onto IMA website (April 2013)

Discontinuous Galerkin Methods for Solving Elliptic and Parabolic Equations: Theory and Implementation

Béatrice Rivière
SIAM 2008, 190 PAGES
PRICE $57.00 (PAPERBACK) ISBN 978-0-898-71656-6

This book is part of the series of books 'Frontiers in Applied Mathematics'. It is aimed mostly at Mathematicians working on solving various Partial Differential Equations numerically. The first chapter is accessible to undergraduates but the rest is at a much higher level.

The book is organised into three sections: Elliptic Problems (Chapters 1–2), Parabolic equations (Chapter 3) and Applications (Chapters 4–8).

Chapter One introduces the Discontinuous Galerkin (DG) method using a single dimension elliptic equation to present the ideas as simply as possible. It is made very clear from early in the chapter that knowledge of the Lebesgue measure and basics of Sobolev spaces are assumed. The following classes of DG methods are defined, based on the values of various parameters: Symmetric Interior Penalty Galerkin (SIPG); Non-Symmetric Interior Penalty Galerkin (NIPG) and the Incomplete Interior Penalty Galerkin (IIPG). The remainder of the chapter considers the detailed analysis and calculations of a simpler case of DG.

Chapter Two uses an elliptic equation in two and three dimensions as an example. Vector methods and aspects of Sobolev space are introduced and the DG methods are studied in some detail, including software implementation details. The Local Discontinuous Galerkin (LDG) method is introduced. At the end of the chapter the DG methods are compared to the Finite Element method so that the advantages of each can be appreciated.

Chapter Three demonstrates the approach when the equation is a pure parabolic type where first space and then time variables have to be discretised. Chapter Four considers parabolic equations that include convection. Chapters Five to Eight consider various applications of these ideas: Linear elasticity, Stokes flow, Navier-Stokes flow and Flow in Porous Media.

At various points in the book the author points out areas of the theory where there are existing opportunities for research in the subject due to gaps in the theory at the time of writing.

This book is clearly aimed at postgraduate and research mathematicians who are interested in recent advances in numeric methods of solving PDE using discontinuous Galerkin methods. I would recommend it for such an audience.

John Bartlett CMath MIMA
Book review published directly onto IMA website (February 2013)

Probabilistic Boolean Networks: The Modeling and Control of Gene Regulatory Networks

Ilya Shmulevich and Edward R. Dougherty
SIAM 2010, 267 PAGES
PRICE $59.00 (PAPERBACK) ISBN 978-0-898-71692-4

Advances in genetic sequencing in the late twentieth century have been accompanied by an increased emphasis on the factors influencing how and when genes are expressed. For example, a skin cell and a liver cell contain the same DNA but regulate it differently, leading to divergence in gene expression and thus distinct forms and functions for the cells. This timely book discusses the use of probabilistic Boolean networks as a systems-level model of such interactions.

The first quarter of the book develops the concept of gene regulatory networks as discrete valued dynamical systems from basic principles. This part of the book has few mathematical prerequisites beyond familiarity with Boolean notation and Markov chains, and new concepts are clearly defined.

Later chapters cover more advanced topics such as the inference of network structure from experimental data, and models where network updating is not synchronous. Algorithms for computational network analysis, together with theorems and lemmas, are set out in a more formal fashion. Some of the proofs here appeal to results from advanced-undergraduate level probability and stochastic processes, but their role is usually explained so readers without a background in probability can still follow the logic of the derivations.

This text focuses on modelling techniques and contains very little biological background, although it does make use of real-world examples to motivate the development of particular techniques. It is clearly written, with generous provision of diagrams, tables and graphs throughout to make difficult content more comprehensible. My only real criticism is directed at the index, which is unhelpful and lacks any cross-referencing, making it harder to dip into particular sections of interest or to revise the groundwork of more advanced topics.

Anyone with a moderate grounding in probability and an interest in systems-level biological modelling will appreciate this book, while students in computational biology will find the extensive bibliography invaluable for further reading.

Paul Taylor AMIMA
Book review published directly onto IMA website (February 2013)

• A Guide to Monte-Carlo Simulations in Statistical Physics (Third Edition)

  This is a graduate level text that deals primarily with Monte-Carlo simulation of complex physical systems encountered in condensed-matter physics and statistical mechanics. It also provides a very brief overview of some alternative computer simulation methods of use in statistical physics, such as molecular dynamics, quasi-classical spin dynamics, dissipative particle dynamics, lattice gas cellular automata and others. The emphasis however, is firmly on various Monte-Carlo simulation approaches to lattice based systems, especially Ising spin type models, and off-lattice systems, exemplified by binary fluids and polymer mixtures.

• A Mathematical Tapestry: Demonstrating the Beautiful Unity of Mathematics

  A Mathematical Tapestry combines some practical recreational mathematics, in particular paper folding constructions, with deep theoretical ideas in geometry, number theory and group theory. This more than justifies the subtitle Demonstrating the Beautiful Unity of Mathematics.

• A Transition to Advanced Mathematics: A Survey Course

  This text is intended to aid students in the move from a calculational, or operational, approach to mathematics to a more conceptual, proof based approach, and also to provide a broad overview of undergraduate mathematics. Chapters cover, in turn, the basics of mathematical logic, an introduction to abstract algebra via group theory, number theory, real analysis, probability and statistics, graph theory and complex analysis.

• An Illustrated Guide to Relativity

  An Illustrated Guide to Relativity explains Einstein’s Theory of Relativity but largely without the equations found in traditional texts. It does this mainly by means of space-time diagrams and cartoons. To an extent it succeeds although the diagrams themselves become quite complex in the more advanced parts of the book, particularly on Lorenz transformation.

• An Introduction to Metric and Topological Spaces (Second Edition)

  Second editions of maths textbooks occupy a strange place in the literary universe. They are not really equivalent to a ‘Greatest Hits’ album, on which only the best examples from a long career survive. Nor can they be considered as being analogous to a Director’s Cut of a movie, in which creativity is given free reign over commercially-dictated constraints on the maximum time of the film.

• Calendrical Calculations (Third Edition)

  Reingold and Dershowitz present a comprehensive review of calendars, and it is suitable for all people who have an appreciation for mathematics and/or history.

• Cows in the Maze – And Other Mathematical Explorations

  The book is an eclectic mix of mathematics selected from Ian Stewart’s columns in Scientific American. It is the third such collection he has written. The book offers a wonderful insight into the range of diverse topics that mathematics as a subject has to offer.

• Data Analysis and Graphics Using R: An Example-based Approach (Third Edition)

  Much has been made over recent years of the need for academic research to contribute to the wider economy. Likewise, there have also been significant debates about the merits and effectiveness of peer review, and what information researchers should provide to facilitate this.

• Decoding Reality: The Universe as Quantum Information

  If a poll was held to identify the most significant written phrase what do you think would win it? Perhaps something from a famous poem about how one should treat triumph and adversity? Or maybe something from Shakespeare about which is the noblest path of action?

• Essential Math Skills for Engineers

  Mathematics is at the heart of engineering design. So states the author, Clayton R. Paul, a professor of electrical and computer engineering at Mercer University, in Macon, Georgia. I expect readers of this magazine are likely to agree, though I’ve known a few engineers who wouldn’t!

• Famous Puzzles of Great Mathematicians

  This book essentially looks at puzzles from recreational mathematics that have been tackled by leading professional mathematicians. The criteria for classifying problems as ‘puzzles’ is that the questions are easy to understand but often require advanced mathematical techniques to solve. Some of these were posed in antiquity but the complete solution is accessible only with modern mathematical techniques and computing resources.

• How to Guard an Art Gallery and Other Discrete Mathematical Adventures

  ‘How to Guard an Art Gallery and Other Discrete Mathematical Adventures’ models solutions to a variety of problems - what is the largest number of pizza slices that we can make with n straight lines, how does a computer configure the best arrangement of pixels to represent a straight line, what is the minimum number of guards needed to guard an art gallery?

• Loving + Hating Mathematics: Challenging the Myths of Mathematical Life

  Mathematicians are different from other people, lacking emotional complexity. Mathematics is a solitary pursuit. Mathematics is a young man’s game. Mathematics is an effective filter for higher education.

• Mathematics in Victorian Britain

  Mathematics in Victorian Britain is a collection of essays edited by Raymond Flood, Adrian Rice and Robin Wilson.

• Mathematics of Social Choice: Voting, Compensation, and Division

  This book is an introduction to, as the title suggests, the mathematics of voting, compensation and division. Each section is self-contained, consisting of short and snappy chapters without being over-concise, and accompanied by mercifully doable exercises which not only tie in well with the text, but are mostly provided with that rare luxury of worked solutions in the back.

• Modelling and Reasoning with Bayesian Networks

  One of the key themes underlying mathematics, and especially mathematical proof, is that of bringing together separate elements and combining them so that they tell a whole new story. Whether it’s in the common theme that unites two apparently disparate branches of work, or in the combination of approaches that together create a complicated proof, amalgamating pieces of evidence (or knowledge) in a reasoned fashion is a critical aspect of the continued progress of mathematics.

• Multiagent Systems: Algorithmic, Game-Theoretic and Logical Foundations

  One of the characteristics of society is interaction, with many different people coming together either to achieve a common goal, for example electing a government, or to compete with each other, for example in a business context.

• Networks, Crowds, and Markets - Reasoning about a Highly Connected World

  The growth of connectedness in modern society in recent years seems to have escalated at a spectacular rate. The rapid technological growth of the internet and global communications, as well as the spread of epidemics and financial crises, affects the wholeworld with surprising speed and intensity.

• NIST Handbook of Mathematical Functions

  How do you improve on perfection?The Handbook of Mathematical Functions edited by Abramowitz and Stegun (A&S) and produced for NIST (then known as the National Bureau of Standards) in 1964 has been the most highly cited of NIST’s publications. Indeed it was one of the standard references at my workplace and I personally found it invaluable.

• Number-Crunching: Taming Unruly Computational Problems from Mathematical Physics to Science Fiction

  In 1841 Augustus De Morgan challenged his students to calculate the real root of a particular cubic equation to more than thirty decimal places – which they did! Richard Feynman once said, “For my money Fermat’s theorem is true” after having produced a probabilistic ‘proof’ of the theorem!

• Numbers Rule: The Vexing Mathematics of Democracy, from Plato to the Present

  There are inherent problems and paradoxes when the choices of a number of individuals need to be combined to make one collective decision. With the recent referendum on voting reform such issues are topical today, but they actually go back to antiquity. Szpiro writes from a historical and mathematical perspective. He also looks at the principal characters and gives a short biography of each, putting their ideas into a social context.

• Numbers: A Very Short Introduction

  This beautiful 230 page paperback is one of a series of 260 Very Short Introductions to a variety of topics, from Aristocracy, through Quantum Theory to Architecture.

• Numerical Notation: A Comparative History

  Comprehensive, encyclopaedic and scholarly are the first three words that spring to mind when reading Chrisomalis’ mammoth work on numerical notation. Not for the faint-hearted, this thoroughly researched academic tome, with an extensive bibliography stretching to some 30 pages, covers over 100 different numerical notation systems spanning over 5,000 years.

• Partial Differential Equations in General Relativity

  This book is written with two main audiences in mind: physicists with a good knowledge of General Relativity (GR) who wish to gain an understanding of how Partial Differential Equation (PDE theory can be applied to GR; and mathematicians with a good knowledge of PDE theory who want to understand how it is applied to GR.

• Professor Stewart’s Hoard of Mathematical Treasures

  Professor Stewart’s Hoard of Mathematical Treasures is the latest collection of puzzles, jokes and mathematical snippets by Ian Stewart, FRS, CMath FIMA, Professor of Digital Media at Warwick University. This collection is a sequel to his very successful Cabinet of Mathematical Curiosities and there is no drop in quality from the previous work. Over many collections (some from his column in Scientific American) Professor Stewart has developed an engaging and irreverent style featuring lots of puns and a series of recurring themes.

• Quantum Field Theory

  This book provides a complete introduction to quantum field theory and the elementary particles. It is set at the level of graduate students who have covered special relativity and quantum mechanics. It covers, amongst other areas, the unification of forces, super symmetry, the renormalization group, quark and gluon scattering, and non-peturbative physics (magnetic monopoles and instantons).

• Riot at the Calc Exam and Other Mathematically Bent Stories

  The intention of the book is given by the blurb on the back which runs as follows:
  “What’s so funny about math? Lots! Especially if you’re mathematically bent. In the world of Colin Adams, differential equations bring on tears of laughter. Hollywood producers hire algebraic geometers to punch up a script. In this world, math and humor are synonymous. ‘Riot at the Calc Exam’ is a proof of this fact."

• Routes of Learning: Highways, Pathways and Byways in the History of Mathematics

  In this volume Ivor Grattan-Guinness collects together a range of papers spanning forty years of his distinguished career as a historian of mathematics. The central theme linking chapters in the first two sections (the ‘Highways’ and ‘Pathways’ of the subtitle) is the place of history in mathematical education. The author criticises accounts which conflate ‘history’ (the development of a particular piece of work) with ‘heritage’ (the impact of that work on future mathematics).

• Secret Days: Codebreaking in Bletchley Park

  Asa Briggs, the eminent historian, has written this book about his memories of his time as a code-breaker at Bletchley Park, or BP as it was known to those who worked there, during the years 1943 to 1945.

• Soliton Equations and Their Algebro-Geometric Solutions (Volume II: (1 + 1) - Dimensional Discrete Models)

  One definition of the soliton is “a pulselike nonlinear wave (solitary wave) which emerges from a collision with a similar pulse having unchanged shape and speed”. More informally it is a “self-reinforcing solitary wave that maintains its shape while it travels at constant speed”. The name is derived from ‘solitary wave solutions’. The phenomenon was first described by John Scott Russell who observed such a wave on a Scottish canal in 1834.

• Structure and Randomness: Pages from Year One of a Mathematical Blog

  Terence Tao is a distinguished mathematician, perhaps best known for his work in combinatorics and number theory, linked especially to the theory of arithmetic progressions of prime numbers. In 2007, he turned his homepage into a weblog, and this book collects some of his online writings which first appeared there. In the book’s collection of some of these blogs, it sketches out unusual proofs for classical theorems, the texts of three of his invited lectures, a selection of discussions of open problems, and a few number curiosities.

• Symmetry in Chaos: A Search for Pattern in Mathematics, Art and Nature (Second Edition)

  Symmetry and chaos seem unlikely bedfellows; yet Field, from the University of Houston, and Golubitsky, from Ohio State University, have produced a book full of beautiful pictures by combining the two. To quote from the Introduction: “Our pictures are created by merging symmetry and chaos. At first sight this seems paradoxical: a merging of order and disorder or yin and yang”.

• The Best Writing on Mathematics 2010

  After reading this wonderfully crafted book, I put pen to paper somewhat apprehensively to write a review of the ‘best writing’. The book is divided into six parts; Mathematics Alive, Mathematics and the Practice of Mathematics, Mathematics and its Applications, Mathematics Education, History and Philosophy of Mathematics and Mathematics in the Media, offering a selection of articles by various authors publish during 2009. With such a great diversity of writing I found myself loving some of the articles, reading others with interest and skipping swiftly over a few, purely due to personal interest and nothing to do with the quality of the article itself. That’s the beauty of the book, you can pick out what appeals to you.

• The Blind Spot: Science and the Crisis of Uncertainty

  A fair number of authors have the ability to explain complicated ideas in simple terms, but William Byers also has the rarer gift of taking the almost banally familiar and revealing its hidden depths and complications. Mathematicians manipulate fractions on a daily basis and can quickly forget how bizarre the idea of writing one number above another may appear to a learner encountering them for the first time.

• The Num8er My5teries - A Mathematical Odyssey through Everyday Life

  Marcus du Sautoy’s latest book The Num8er My5teries is written for the general reader. The book bursts with creativity, analysis and explanation in a clear non-specialist style. Complex issues in the subject become accessible as he exposes readers to the big ideas in mathematics.

• What's Luck Got to Do with It? The History, Mathematics, and Psychology of the Gambler's Illusion

  Joseph Mazur’s book takes us on a fascinating journey looking at the misconceptions involved in gambling. The reader learns the history of gambling, the way mathematicians analyse luck and the psychology that affects gamblers.