Mathematicians & Bureaucrats

All (most) math departments have a day where school students come to the department and you do math-y activities with them. In Ghent this day is called UniMath and happened today. My colleague Zhirayr Avetisyan and I contributed a riddle to it. Maybe it was a bit too hard, but I like what we ended up with. Here it is. Have a look at the city map of Ghent to see which locations we used (and how much we distorted reality, so that the map is a square).

It is well-known that mathematicians and bureaucrats are archenemies of all times. For mathematicians normally take a hard problem and make it simpler in order to render it solvable, whereas bureaucrats take pride in making otherwise simple problems into very hard ones, so that they become effectively unsolvable.

Below is an abstracted map of the city of Ghent with a selection of landmarks (text) and routes (lines) between them. A group of mathematicians leaves the Sterre campus of UGent in the evening, with the aim of enjoying their time together in the city. Right after that, several bureaucrats leave the city hall at Zuid simultaneously and move each in independent directions, with the aim of catching the mathematicians and preventing them from having fun. Mathematicians always move as a single group, whereas each bureaucrat acts as a separate player. Each turn every player (first the group of mathematicians, then bureaucrat 1, bureaucrat 2, …, bureaucrat n) moves from their present location to one of the nearest locations along a route on the map. Mathematicians are caught if at any moment they are at the same location as at least one of the bureaucrats.

Question At least how many bureaucrats must be allocated for the mission such that the mathematicians are definitely caught at some point?

Everyone always knows where everyone else is, bureaucrats and mathematicians can choose where to move (as long as it is one step along one route), and the chase goes on for all of eternity.

There are many valid solutions. The riddle above was one example in one of the central works on this research area. You can click here to read the paper (but first find the solution yourself).

Follow the blog!