Cops and Robbers

Recall my recent post about mouse-picking, motivated by a “hidden object” puzzle adventure game that my wife and I played?  We have since moved on to another similar game, Penny Dreadfuls: Sweeney Todd.  We enjoyed this game even more, since it included more challenging puzzles to solve in addition to the hidden object scenes.  (I am still fascinated by how addicting just the hidden object scenes are.)  Those puzzles often have some interesting mathematics hidden inside them.

Before continuing, consider this a possible spoiler warning: this week’s post concerns the final puzzle that you must solve to “capture” Sweeney Todd to finish the game.  I am always looking out for puzzles or problems that might serve as a vignette for students to investigate some cool mathematics, or perhaps to study as a computer programming project.  But you might find this puzzle interesting, too, and want to solve it yourself.  You have been warned.

In the puzzle, you are a detective chasing Sweeney Todd through the streets of London, as in the following picture:

Final Puzzle

Initial state of the final Sweeney Todd puzzle.

You are the detective in blue, and Sweeney is red.  You and he alternate turns, where a turn consists of moving to an adjacent vertex.  You move first.  You win if both you and Sweeney occupy the same vertex.  I wrote a simple Java applet where you can play the game here.

(Note that you don’t really “win” this version of the game.  After each of your moves, Sweeney will immediately move according to a deterministic algorithm.  If you catch him after your turn, he will still move one edge away on his turn.)

After working out a solution, and being pleased by the interesting mathematics involved, I checked out some online walkthroughs of the game that describe how to catch Sweeney.  Interestingly, all of them essentially suggest to “just keep moving towards him and try to back him into a corner.”  This rather vague advice fails to capture a necessary part of the solution, namely how important that diagonal edge in the center of the graph is.  It is not difficult to show that if neither you nor Sweeney traverses that diagonal edge, then Sweeney can evade you indefinitely.

To see this, consider the graph with the diagonal edge removed, and consider the distance (i.e., number of edges on the shortest path) between you and Sweeney, which is initially 4.  The key observation is that after every turn, that distance changes by +1 or -1.  Thus, you can never capture Sweeney on your turn, since your distance from him will always be odd.  And on Sweeney’s turn, if he is ever just a single edge away from you, there is always another edge he can traverse to increase his distance to 2.

It turns out that this problem has been studied quite extensively, and is typically referred to in the literature as “pursuit-evasion,” or “cops and robbers.”  An early paper by Aigner and Fromme (“A Game of Cops and Robbers“) is available online and describes the basic game and its many variants.  I found it interesting that almost all of the papers on the subject, including this one, seem to focus on the so-called passive version of the game, where the robber (Sweeney) has the option to not move on his turn.  In this passive version, Sweeney wins, since if you (the cop) ever traverse the diagonal edge, he can stay put for a turn, maintaining the parity of distance in the grid subgraph.

Another interesting paper that applies here but unfortunately requires a journal subscription is by Neufeld and Nowakowski, “A game of cops and robbers played on products of graphs” (Discrete Mathematics 186 (1998) 253-268).  They generalize the result that the active robber (that must move on each turn) can evade indefinitely on the graph product of any two trees, of which the grid above is a special case, being the product of two paths of length 5.

This entry was posted in Uncategorized. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s