Monday, 16 September 2013

Maidens and Vampires

A recent pub dinner with a friend turned into a rather geeky trading of logic-and-mathematical puzzles.  I have a couple of interesting ones used for interviewing potential undergraduates, and he has some to help make his somewhere-between-primary-and-secondary age pupils think.

One we spent a while discussing was the vampires and maidens problem.  In short, three vampires and three maidens need to travel from one floor to another of a building, using a lift that can carry up to two people.  Some extra constraints: the lift needs someone in it to move (as my friend pointed out, this problem really would be better stated using a boat and two shores, but I guess all those boats are busy moving cabbages and foxes...), and if any maidens are left alone with a greater number of vampires, they get turned into lunch.  Can you come up with a plan to move all six from one floor to another without breaking the rules?

A verbal discussion of the problem very quickly becomes unwieldy, so it wasn't long until my notebook came out and diagrams were drawn.  Based on the diagrams and discussion, there were several interesting observations we managed to make about the puzzle.  The moves going back from the end are a mirror of those from the start (from the start, one or two vampires, or a vampire and a maiden could leave.  To reach the end, one or two vampires, or a vampire and a maiden could arrive).  It also is really important to track where the lift is when drawing pictures, lest you try and teleport a maiden!

Since I've been reading up and thinking a lot about visualising information for clear explanations recently, I thought it'd be fun to try and apply some of that thought to both the problem and solution.  In reality, it's not a very hard problem once you understand it (certainly it doesn't have a hugely branching state space), but I guess for kids it could be used as a good introduction to thinking about enumerating possibilities, of logically structuring thought about a problem, of exploiting symmetries, and drawing insights. Or something.  I also added in the fun challenge of trying to describe this problem through the medium (tedium?) of poetry.

One note, if you Google for this problem you'll find it's usually stated (e.g. in Dara O'Briains School Of Hard Sums) as from the ground floor to the top floor.  For the dual purposes of having the six actors adjacent to the line introducing them, and to make the third line of the poem work, I switched the direction of travel.

Super-high res versions in-case anyone wants to actually turn them into posters (if you do - I'd be interested in knowing if they were useful!  Assume the graphics are licensed CC-By-SA).