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.