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.

1. I am not certain that this problem has been created properly as in the instance specified there would seem to be a solution in 9 moves.

If we take a vampire and a maiden to the top of the lift and subsequently take the vampire back down, then take two vampires up and one back down again then take both maidens up before bringing a vampire down then taking two vampires up and one down and finally two vampires up. This would seem to solve the puzzle in nine steps at no point leaving more vampires than maidens in any one spot. I am assuming in this scenario that somebody has to be in the lift when it moves but this does not seem to be explicitly stated in the rules and if you can move the lift with only the operator in it we can actually solve the problem in five moves i.e. 1 vam and 1 maid up then lift empty down, then 2 maid up then lift empty down and finally 2 vam up.

Can you explain any logical discrepencies with these methods as I cannot see any.

2. Good try, but I think that unfortunately this doesn't quite work - when you take a vampire and maiden up and then bring the vampire back, you have two maidens at the bottom outnumbered by three vampires.

3. 1.V+M to the top, 2.take M down.
3.V+V to the top, 4.Take M down.
5.M+M to the top, 6.Take V down.
7.V+M to the top, 8.Take V down.
9.V+V to the top... Wouldnt that work?

1. No it wouldnt because if you take a v+m to the top and bring the m down and send v+v to the top there isnt a m to bring down if you send two v up you cant bring a m down because there isnt another to bring down so you have messed up step 4

4. After step three you have three vampires at the top so step 4 must be "Take V down". You then have two vampires and three maidens at the bottom so taking two maidens up leaves one maiden outnumbered at the bottom.

5. 1: V+M up
2: V goes down
3: M+M up
4: M goes down
5: M+V up
6: V goes down
7: V+V up
8: V goes down
9: V+V up
3 vampires
3 maidens

6. I've done it in 9 moves though

1 vm up
2 m down
So that leaves 2v 3m at the bottom. V at the top
3 vm up
4 m down
So that leaves v 3m at the bottom. 2v at the top
5 vm up
6 m down
So that leaves 3m at the bottom. 3 v at the top
7 mm up
8 v down
That leaves v m at the bottom. Vv mm at the top
9 vm up

7. why can't you do v+m on each step? would only need 3 steps then.

8. If we do v+m on each step, how does the lift get back to the bottom for the next couple?

9. i agree on 9 moves,
lift ----- bottom ----- top
vv ------ vmmm
v ------- vmmm ------ v
vm ----- vmm -------- v
v -------- vmm ------- vm
vm ----- vm ---------- vm
v -------- vm --------- vmm
vm ------ v ----------- vmm
v --------- v ---------- vmmm
vv --------------------- vmmm

10. After the fourth step, when the lift containing vm is at the top, there are two vampires and one maiden at the top.

11. 1. VM up
2. M down
3. VM up
4. M down
5. VM up
6. M down
(Now 3 Vs up, 3 Ms down)
7. MM up
8. V down
(Now 2 Vs and 2 Ms up, one each down)
9. MV up

12. I agree with anonymous (20 June) that's how I did it, without breaking any of the rules. What gets me is the mathematician on Hard Sums who said 11 moves is the smallest number of moves. He's meant to be a matematician and is meant to give the definitive answers. If we can't trust his competence to get it right what's the point in watching?

13. Jen - I'm afraid that after step 3 you have two vampires and one maiden at the top. Anon- there is the same issue with the proposal you mention.

1. Ah yes. I was solving it like the wllf, goat and cabbage one, like the vampires would only kill if LEFT with fewer maidens. I see, thanks :)

2. Ah yes. I was solving it like the wolf, goat and cabbage one, like the maiden was only in danger if you left her there for a turn. Ok, thanks :)

14. 1. VM up
2. M down
3. V up
4. 0 Down
5. MM up
6 O down
7 VM up

Unless I missed the rules about people have to come down

15. Try this one now: FOUR vampires and FOUR maidens are at the foot of a tall building and wish to get to the bar on the top floor.  The lift only holds THREE people (for convenience we class 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?