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?
A very occasional blog about maths things which interest me.
Monday, 28 May 2012
Sunday, 20 May 2012
"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 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.
Sunday, 13 May 2012
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.
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.
Saturday, 5 May 2012
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
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?
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?