An interesting puzzle from MathsJam

by cp!

MathsJam?

MathsJam is a monthly getting-together of people who like talking about maths in a pub.

It happens on the second-last Tuesday of each month.

The Newcastle one takes place at the Charles Grey, near the Monument.

There are loads of them!


View MathsJams current and potential in a larger map

The princess-in-a-castle puzzle

The setup goes like this:

The princess-in-a-castle puzzle

And the puzzle is:

Is there a strategy the prince can follow to guarantee he looks in the room the princess is sleeping in within a certain (finite) number of days?

Step 1

Make the problem smaller

rooms 1 1 2 2 1--2 3 3 2--3 4 4 3--4

Step 2

Make the problem interactive

Use pen and paper and then, if you're me, make a simulation of the puzzle on the computer.

Step 3

Make up some notation

The game, formally

Let $G$ be the graph corresponding to the layout of the castle. Give every vertex a unique label.

The prince's strategy is a sequence $V_1, V_2, \dots$ of labels of vertices: on night $i$, the prince looks in the room with label $V_i$.

A room is occupiable on a particular night if there is a sequence of rooms the princess can choose which puts her in that room on that night, and differs from the prince's strategy every previous night.

Mark occupiable rooms with a $Y$ and non-occupiable rooms with an $N$.

  1. On the first night, mark all rooms with $Y$; let $i:=1$, then repeat the following:
  2. Mark room $V_i$ with $N$.
  3. For each vertex in $G$, mark it with a $Y$ if there is an adjacent vertex marked $Y$ in the previous night's state; otherwise $N$.
  4. If all vertices are marked $N$, done. Otherwise, let $i:=i+1$ and return to Step 2.

Observations

Step 4

Be excellent and solve the problem

An algorithm to find which room to pick

  1. Mark all rooms with $Y$.
  2. For each vertex $V$ marked $Y$ in the current state, compute the state the graph would be in after looking in $V$.
    • If that state has been seen before, ignore and return null.
    • If not, remember the new state and repeat Step 2 on the new state.
  3. Of the rooms looked at in Step 2 which didn't return null, return the one with the shortest strategy.

An optimisation

An automorphism, or symmetry, of a graph $G=(V,E)$ is a permutation of the graph $\sigma$ such that there is an edge $(u,v)$ in $\sigma G$ if and only if there is also an edge $(\sigma u , \sigma v)$.

rooms 1 1 2 2 1--2 3 3 1--3 4 4 2--4 5 5 2--5 6 6 3--6 7 7 3--7
$ \displaystyle{\xrightarrow{\sigma=(2 3)(4 6)(5 7)}} $
rooms 1 1 2 3 1--2 3 2 1--3 4 6 2--4 5 7 2--5 6 4 3--6 7 5 3--7

So we can consider states of the graph up to symmetry, greatly reducing the running time of the algorithm.

Which graphs are solvable?

Thanks!

Longer blog post about the puzzle at http://checkmyworking.com/2011/12/solving-the-princess-on-a-graph-puzzle/.

/

#