A tree which is not a tree

Graph theory is perhaps my favourite area of mathematics.  It features diverse and appealing modes of reasoning, and many of the results are relatively accessible,  rather than requiring a lot of theory.  

A tree is a special kind of graph, like that above (the numbers serve only to identify the vertices).  Technically a connected graph is a tree if there is exactly one path connecting any two vertices, or equivalently the graph contains no cycle. In lay terms this means a diagram where points are joined by lines.in such a way that there is no loop.  The branching is like the branches of a tree (in the natural sense of the word) or of a family tree, as one sees in the diagram below, where one of the vertices is chosen as a root.

There are lots of results one can prove about graph-theoretical trees.  For example, a tree with n vertices must have exactly n-1 edges.  Trees are particularly useful in computer science.  But what I am interested in today is the definition.  

Books like Robin Wilson's excellent Introduction to Graph Theory motivate the definition by referring to family trees and botanical trees. Now there is a nice sycamore tree in our garden:

But this is not a tree in the graph theory sense!  It contains a cycle:

Two squirrels could climb to the top of the tree taking different routes!  And that's impossible in a graph which is a tree, where there is only one route between any two points.

So what's gone wrong?  Why is my tree not a tree?  Why does the mathematical definition which seeks to encapsulate the "tree-ness" of trees, exclude this perfectly respectable specimen of a tree in our garden?

Well, mathematics is about abstraction.  The definition of "tree" abstracts something typical of real trees, which does reflect the nature of branching (our sycamore is slightly unusual).  It leads to a very rich branch of graph theory, with many applications.  So it's a good definition.  (But it doesn't exactly fit family trees either.  If you go back a few generations you get connections which give loops, when the same person is an ancestor in two different lines.  Otherwise we would each have far more ancestors than all the humans who have ever lived.)

Here's another illustration.  If I take a square piece of paper, it has four corners.  Let's get rid of the corners by cutting them off with scissors (cutting off a triangular piece at each corner).  I've taken four away from four: mathematically I might expect to have zero corners left, but in fact I have eight since the remaining paper forms an octagon.  So 4-4=8 in this situation.  (Peter Flom's blog has some other examples where 2+2 is not 4.)

So does maths fail?  No.  When I was younger I'd have felt that these examples of arithmetic failure were contrived, obviously artificial and not to be taken seriously.  I now think I was wrong.  These are real examples: it's mathematics that is contrived.  We abstract the rules of arithmetic from a world in which they don't always apply, to create a system which is enormously useful.  The power of mathematics comes from simplifying the real world.  The mathematical idea of a tree is powerful, even if it excludes some legitimate trees.  Arithmetic is powerful even if it doesn't apply to some real-life situations. 

So it's amusing that our sycamore tree is not a tree, but it isn't a flaw in graph theory!

Dara's Big Mistake

I've just watched the latest (and final) episode of Dara O'Briain's School of Hard Sums, with Andi Osho again demonstrating a remarkable ability to get straight to the solution by what appeared to be inspired guesswork.  If I were doing undergraduate groupwork, I'd want her in my team!

SPOILER ALERT: If you're planning to watch this programme (it's repeated over the next few days) you may not want to read this yet as I give some hints as to what happens (though I don't give away the maths)..

The final problem involves runners going round a race-track at different speeds and asks how long it is after the start before all three runners are again together.  Dara produces reams of incomprehensible algebra to get an answer in which he doesn't have full confidence - he presents it reluctantly, convinced that he has gone wrong.  His delight when he finds his answer is correct was the highlight of the series.

I think Dara got it badly wrong.  He didn't check his answer!  His algebra was complex but it gave a solution: it would have taken only a moment to see where the three runners were at the time in question and establish that they were all together.  ((OK, only a partial check: it might not have been the first time, but it would at least have shown that his answer was plausible.)

In any maths problem, if you can check your answer is valid, it gives you confidence in your solution.  I worked for many years in the mathematical modelling of industrial plant.  There were essentially two kinds of problems.  Engineers wanted either to find the steady state of the model - the normal plant operating condition when nothing is happening to disturb it - or to find out what happened dynamically when some disturbance was applied (say if a pipe broke and the cooling system failed).

The models were essentially defined by a set of differential equations.  Finding the steady state involved finding values such that all the derivatives were zero - that is, finding a zero of a system of a couple of thousand non-linear equations.  Not easy  - sometimes the equation-solving algorithms failed and we were reduced to starting from a random initial state and running the model for a very long time in the hope that it would naturally arrive at the steady state.  But if the algorithm gave a solution, you could test it by plugging the numbers into the equations and making sure they all gave you zero.

But running dynamically involved numerical integration, and there is no simple way to check your answer!  Since numerical integration can give completely incorrect results (try integrating dx/dt = -1000x by Euler's method with step-size 0.01, say, to see output which is not only quantitatively but also qualitatively completely wrong) this is a serious problem.  (There are ways one establishes confidence in the output from numerical integration, but they aren't as simple as plugging the answers in to the equations to check that you get zero!)

Dara's algebra may or may not have been right.  But if he had checked where the runners were after the time he had deduced, he could have had a lot more confidence in his calculations.  Of course, it wouldn't have made such good TV.

Atiyah and Villani at Tate Modern - the value of blackboards

A wonderfully stimulating afternoon at the Tate Modern gallery this afternoon, for a mathematical event in a series entitled "Topology".  The afternoon had two parts - a showing of the film "Au Bonheur des Maths" by Raymond Depardon and Claudine Nougaret, followed by discussion between Michael Atiyah and Cédric Villani, two mathematical superstars, chaired by Ian Stewart.

The film comprised a series of short statements by mathematicians, essentially presented in black and white as talking heads, though Villani alone used the blackboard to communicate (more on this later).  They all had interesting things to say.   I was slightly puzzled by Atiyah's comment afterwards on the diversity of the mathematicians: most seemed to be white, male and middle-aged, and presenting similar views of the subject.

The discussion, ably chaired by Ian Stewart, was absorbing.  It helped that the questions from the audience were all interesting (or were made interesting by Villani and Atiyah).  It was being recorded, and I hope the result will be made widely available.

There were so many interesting ideas that I can only pick out a few that resonated with me.   One was the extent to which mathematics is a frustrating activity: 'You spend most of your time thinking "I can't understand this"' (and if that's the experience of Stewart, Atiyah and Villani, what is it for the rest of us?)  This is something that must influence the characters of mathematicians: how can you be arrogant when you are always wrestling with problems you can't solve?  It must be off-putting for undergraduates who found mathematics easy at school to find at university that there are hard problems on which they get stuck: appreciating that being stuck is the natural state of even the greatest mathematicians, and isn't a sign of one's inadequacy, might help keep them in the profession.  So I'll be quoting this to my students.

I was really impressed by the evident breadth of knowledge of both Atiyah and Villani.  They had read Kepler; Villani told us about Voltaire's comment that Kepler's achievement was a humiliation for philosophy in that such a deluded thinker could make such great discoveries.  Both seemed keen on reading the writings of the great mathematicians of the past.  Villani made fascinating comments about the different ways in which the composers Xenakis and Ligeti made use of maths, and showed how a work of Ligeti refutes a remark in Euler's writing on music. When there is such a focus on research outputs that reading outside one's immediate subject can seem like a luxury one can't afford, I found Atiyah and Villani inspirational in their range of serious interests.

There were insights into similarities between mathematicians and artists - both proceed by breaking rules (for example, non-Euclidean geometry arising by discarding a previously unchallenged axiom) and both work with a mix of individual and collaborative activity.  There was wisdom on teaching - the personality of the teacher is the most important factor, and Villani commented that saying that we need more people to study science is not the best way to encourage young scientists.

Villani was asked about the "enemies" a mathematician faces, and identified three - lack of imagination; a priori ideas, which you have to eliminate in order to make progress; and too much information, hiding the things that really matter in fog.  Stewart told a fascinating anecdote about a friend discussing three-dimensional topology over the phone with a mathematician who had been blind since birth (a remarkable idea in itself) and noting that the blind mathematician was obviously visualising the problem very clearly but without taking any single point of view - a very interesting concept.  There was discussion of ugliness in mathematics - with, I think, agreement that a good proof is about understanding, and a proof which doesn't tell you why something is true is inherently unsatisfactory.

Artists in the audience asked some of the most interesting questions.  One was about symbols - how do mathematicians choose their symbols?  Villani's answer made me aware just how important choice of symbols can be - they permit a level of automatic checking and most symbols carry meaning for the reader which helps comprehension.  (I remember struggling with the German letters symbolising group varieties in an algebra book: I couldn't immediately tell which was which and, not surprisingly, I never got on top of the material. My fault, not the authors: I should have spent time copying the letters until I could read them at a glance!)

The final question, again an insight into how the practice mathematics relates to that of the visual artist, was about the "extraordinary mark-making" mathematicians do on blackboards, and whether this can survive in the digital age. Atiyah's answer agreed on the importance of the hand in doing maths, and that communication of mathematics involves body movement, props, blackboards - the garnish that makes something palatable.  Villani, noting that blackboards are now not always available in lecture rooms, felt that the blackboard is unrivalled: much more than with a computer, one can improvise, erase, keep some material and lose other bits; it forces you not to overflow, and when  you're frustrated, you can bang your head on it!

This was an amazing afternoon, rich in provocative ideas.  The mathematicians' passion came across; there were insights about mathematics, art and music.  If these notes are garbled, it was because there was so much to think about!  I do hope the recording will be made available, even though it will probably show that I have misunderstood and misinterpreted a lot of what was said.  I have rarely spent such a stimulating afternoon in a gallery (and that is a very strong statement).

Vampires, maidens and Angela, my old matchbox computer

As promised in my post a fortnight ago, I'm returning to the Vampires and Maidens problem from Dara O'Briain's School of Hard Sums.  Thinking about it took me back to the matchbox computer I made as a teenager: its modus operandi would have solved this problem.

Like so many of my mathematical interests, this one began with a Scientific American column by Martin Gardner (or perhaps I encountered it in one of his books).  The theme was that a machine can learn by experience.  I had a very limited knowledge of computers, naturally, and one of the things people said at the time that distinguished human from machine intelligence is that a machine's programme is hardwired and cannot learn from its experience.  Gardner's article showed that this is not so.

His example (if I remember correctly - I am often surprised how wrong my memories are when I check up, so I won't!) was a simple game with chess pawns on a 3x3 board.  I implemented it for Nim's Game, with three piles of three matchsticks.  (Why matches?  Because I had a lot of matches to use up, as we will see.)  In Nim's game, players take it in turn to remove as many matches as they wish (but at least one) from any single pile, and the player who takes the last match loses.  (Or wins- counter-intuitively, it makes little difference to the strategy which version you choose.)

There is a mathematical strategy for Nim's game, but my "computer" didn't do it that way.  I enumerated all the different positions, from (0,0,1) to (3,3,3).  I reckon there are nineteen essentially different positions, with (0,0,1) being an immediate loss for the player about to move.  These days, one would do this on a real computer, but this was long before teenagers had access to computers so, following Gardner, I labelled an empty matchbox for each position.  In each box I placed a counter indicating a legal move from that position, so for example the box for (3,3,3) would contain counters for (2,3,3), (1,3,3) and (0,3,3), representing the three possible moves: one can take 1,2 or 3 counters from any one pile.

The matchbox "computer" is now ready to play against a human.  When it is the computer's turn, one opens the box for the current position and draws a counter randomly: that is the computer's move.  The human then tales their turn, and then opens the box for the next position and draws another counter.

The beauty of this is that the machine can learn from its mistakes!  When the machine loses, we discard the last counter chosen.  (All other counters are replaced in the box they were drawn from.) Consequently the computer will never make the same final losing move twice.  So, for example, consider the box (0,0,2).  There are two moves: to (0,0,0) (immediate defeat) or (0,0,1) (immediate victory).  The first time the machine reaches this position, the counter for (0,0,0) may be drawn.  The machine will lost that game (from a position where any human would have won), but that counter will be discarded, and the machine will always win from that position in future.

When a box is empty, that means the machine knows that there is no move from that position that does not result in eventual defeat (assuming perfect play from the opponent), so it resigns.  As a consequence, counters from boxes which allow the opponent to move to that position will begin to be removed.

After a reasonable number of games, the only counters left in any boxes will be those which never lead to defeat.  The machine will start playing randomly, but will end by playing perfectly!

This fascinated me.  I called my machine Angela, for "A Nim's Game Experience Learning Automaton".  (I'm not sure "automaton" is right for a device which requires one physically to draw counters from matchboxes, but it served the needs of the acronym.)

What does this have to do with the Vampires and Maidens problem?  Remember that we have three vampires and three maidens at the foot of a building, needing to get to the top in a lift which can only carry two people at a time and which needs one person inside to operate it.  If at any time, vampires outnumber maidens in any location, then something unspeakable happens.  How can all six safely get to the top?

Well, the matchbox computer idea will solve this.  As suggested in my previous post on this problem, w can enumerate the possible positions - these will be of the form (v,m,l) where v is the number of vampires at the bottom, m is the number of maidens at the bottom and l is the position of the lift.  So v and m are between 0 and 3 and l is -1 for lift at ground level and +1 for lift at the top.  The problem is to go from  (3,3-1) to (0,0,1), where we fail if at any stage m is non-zero and m is m<v.

Now create matchboxes for each position, and use counters to indicate possible moves.  From the starting position (3,3-1) there will be five possible moves, to (2,3,1), (1,3,1), (3,2,1), 3,1,1) and (2,2,1). (Two of these leave maidens outnumbered at the bottom.)  We then begin at the starting point and draw a counter, move to the indicated matchbox and draw another.  Any time we reach a failing position, we discard the last counter drawn.

Of course, the counter we draw may take us back to a position we were in earlier.  To avoid looping for ever, we discard any counter which returns us to a state we have previously encountered.

The result is that, eventually, drawing counters at random and backtracking when we fail, we are left with a solution to the puzzle.

What is wonderful, or appalling, about this is that, as with my Nim's Game device, we solve the problem with no deep understanding of the strategy.  On the one hand it is amazing that we can find solutions to difficult problems without any serious thinking about the problem: on the other hand, the standard strategy for playing Nim's Game (which I already knew from earlier articles by Martin Gardner) is better maths!

So is it better to solve problems by mathematical thinking or by the brute force approach of my matchbox computer?

"Tenet" - Galois on stage

I had intended my next post to write more about the Vampires and Maidens problem from the TV programme "Dara O'Briain's School of Hard Sums", but that will have to wait, because I want instead to write about the play I saw a couple of nights ago, in the faint hope that someone might read it in time to see something they would otherwise have missed.

The play is "Tenet", by Lorne Campbell and Sandy Grierson, which is at the Gate Theatre, Notting Hill, London until May 26th.  Actually the full title seems to be "Tenet: A True Story About the Revolutionary Politics of Telling the Truth about Truth as Edited by Someone Who is Not Julian Assange in Any Literal Sense".

The two characters are the young mathematician Evariste Galois and the Wikileaks founder Julian Assange, and the performances by Lucy Ellinson and Jon Foster are truly sensational.   On the evening I went, there was post-performance discussion between the group theorist Peter Neumann and the author Lorne Campbell, which I think was remarkably successful, both for the mathematicians and the lay people in the audience.  The play seems to have been a labour of love for Campbell, who read about Galois ten years ago and had wanted to write about him ever since.

There is a lot of mathematics in the play, and it is presented intelligently and accurately: the story of modern algebra is communicated remarkably well.  But there is much more to the play than that.  There is rich reflection on the nature of truth.  Galois's concern is pure, abstract, essential mathematical truth: if humans had never lived Galois's mathematical structures would still exist (or so I like to think).  Assange's concern is with revealing the truth about the human world in which we live.  And the personal circumstances of both are extremely murky.  We don't know why Galois fought the duel in which he died (if indeed there was a duel) and what we know about Assange are equally complicated.

I went to this play out of curiosity: from the brief plot summary on the website I didn't see how it could possibly work.  It was astonishing: a truly remarkable theatrical experience, with outstanding performances in a quite exceptional play, leaving the audience with much to think about in relation to politics, mathematics and truth (exactly as promised by the subtitle).  It is very rare for mathematics to be central to theatre in this way.  If you can possibly see this play, I strongly recommend you do so.
________________

While on the subject of mathematics in literature, I might also mention a wonderful short story I've just read.  I've enjoyed all the stories in Etgar Keret's Suddenly, a Knock on the Door (recently published in English translation), but anyone who likes mathematics will particularly love the one entitled "What, of this goldfish, would you wish?"  A gem in eleven small pages.

The Vampires and Maidens Problem

The most recent episode of the rather surprising British TV series Dara O'Briain's School of Hard Sums was, I felt, the most successful yet.  (The programme is currently being shown on Channel Dave in the UK on Mondays at 8pm, with subsequent repeats on Dave and Dave Ja Vu.)  The guest in this one was the comedian Andi Osho, who turned out to be a very good intuitive problem solver - has she missed her vocation as a mathematician?

The "hard" problem this week, like most of the problems on the show, is a fairly standard puzzle, dressed in slightly new clothes.  Three vampires and three maidens are at the foot of a tall building and wish to get to the bar on the top floor.  The lift only holds two people (for convenience I am classing vampires as people), and needs one person to operate it.  If ever the vampires outnumber the maidens at any place, they will do something unspeakable.  How can the vampires and maidens all safety get to the top?  For example, if initially two maidens get in the lift together, the maiden left behind will be outnumbered by the three vampires, with disastrous consequences.

My initial reaction is that a top-floor bar serviced by a single two-person lift, which needs someone inside it to operate it, is a spectacularly bad business proposition, but then it is never a good idea to look too closely at the real-worldliness of maths puzzles.

Andi Osho, the students, and Dara O'Briain all found the optimal solution.  I find this problem mildly frustrating in that it seems to me you don't have to have any special insight to solve it.  Once you have started, at each stage you can eliminate any move that leads to immediate disaster.  Since you are looking for the fastest solution, you can also eliminate any move that takes you back to a situation you've already had, since that would mean that you have made no progress.  (From the context in which you have been given the problem, you know that there is a solution.  Problems are much easier if you know they can be solved: another example of how the real world makes life unnecessarily hard for us compared with maths puzzles.)

These rules actually make the problem very simple.  The first two moves must involve taking two people to the top and then one of them returning. If the person left at the top is a maiden, then the two maidens at the bottom will be outnumbered after the second move, so the moves must leave a vampire at the top (and either a maiden or a vampire can have accompanied them to the top).

We now have three maidens and two vampires at the bottom.  If two maidens get into the lift, the third will be sacrificed: if one maiden gets in with a vampire, she will be outnumbered when the lift gets to the top.  So the only way to make progress is to sent two more vampires to the top, and bring one vampire back in the fourth move.

After these four moves we have two vampires at the top and one vampire and three maidens at the bottom.  The only possible move that avoids repetition or disaster is to take two maidens to the top.  And then the only possible progress is to bring back one maiden and one vampire.

This leaves two maidens and two vampires at the bottom.  If one or two vampires go up on their own, the maiden at the top will be outnumbered. One maiden travelling on her own will leave a single maiden with two vampires at the bottom.  So we have to send the two maidens up on their own, and send the vampire at the top back down.  Then two vampires go up, one returns to pick up the final vampire and we have achieved our objective.

My point is that we have solved this problem with no strategic thinking at all.  We have just taken at each step the only move that doesn't lead to immediate disaster or return to a previous position.  Nothing else is needed.  This simple short-term tactic, involving no serious thought, is sufficient to solve the problem, and this is possibly rather unsatisfying!

Of course, we could have used a more clever approach, for example exploiting symmetry and the reversibility elements of the problem.  If we denote the position of the lift as -1 (bottom) or 1 (top) and let v and m be the number of vampires and maidens at the bottom, then the problem is to go from A = (3,3,-1) to B = (0,0,1) where the moves allowed correspond to one or two being transported by the lift car.  The only allowed positions require either v or m to be zero, or v to equal m.  Then there is anti-symmetry between positions like C = (1,1,-1) and D = (2,2,1) - both have one maiden, one vampire and the lift car in the same place - so the sequence of moves which get A to C gives us, in reverse, a sequence of moves that will get from D to B. In the solution I give above, we see that the positions after five and six moves are anti-symmetric; that moves 7 to 11 are exactly moves 1 to 5 in reverse; and the middle move 6, to preserve the symmetry, has to involve one vampire and one maiden.  So symmetry considerations do give us a more elegant way to solve the problem.

The direct approach does remind me of a wonderful Martin Gardner article about machines learning from experience: that will be the subject of my next post.

My favourite maths puzzle

This problem, from Peter Winkler's wonderful  Mathematical Puzzles: A Connoisseur's Collection,  is one of my favourites.  At first sight it seemed impossible that there could be a simple solution, but when I looked at the answer I felt that I really should have been able to solve it for myself.

Let t be the positive square root of 2.  Since I'm writing this on 5th May 2012, I will ask "What is the 55th digit after the decimal point of (1+t) to the power 2012?"

Try to solve it before reading on!

*********

Why does this seem so difficult?  We're raising a irrational number which is a bit more than 2.4 to a very high power and asking for an apparently random digit in the fractional part.  How can we do it?

(1+t)^2012 looks fairly intractable.  We can use the Binomial Theorem to expand it and we will get lots of powers of t.  Even powers are fine, because they are powers of 2, but the odd powers are all irrational and it's hard to see how we can deal with them.

There is a standard trick for getting rid of the irrational numbers.  If we expand (1-t)^2012, then we get exactly the same binomial coefficients but the odd powers have the opposite sign.  So if we were to consider

(1+t)^2012 + (1-t)^2012 (*)

the oddd powers cancel and we are left with the sum of integer multiples of the even powers of t, all of which are integers.  So (*) is an integer.

But how does that help us?

Well, what is (1-t)^2012?  (1-t) is about -0.414, which is less than -1/2. So (1-t) to the power 2012 is less than (-1/2) to the power 2012, which is a very small number indeed.  Since 2^10 is greater than 10^3, (-1/2)^2012 is less than 10^(-670).  So (1-t)^2012 is a very small decimal number beginning with least 670 zeroes.

And so since the second term in the integer (*) is this tiny number beginning with 670 zeroes, so the number we are interested in, being less than an integer by this tiny number, must have a decimal fractional part beginning with at least 670 nines.  So the 55th digit (and another 600-odd after it) must be a 9.

Having seen the solution, one feels that there could have been no other way to tackle this problem.  But I didn't see it for myself.  I've used the problem in a number of Christmas competitions and no-one has solved it yet.  Did you?