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:

There is a castle with 17 rooms in it, arranged in a line.

The princess who lives in the castle sleeps in a different room each night, but always one adjacent to the one she slept in the previous night. She is free pick any room to sleep in on the first night.
A prince would like to find the princess, but she will not tell him where she is going to sleep each night.
The prince can look in a single room each night, with no other restrictions

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

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$.

On the first night, mark all rooms with $Y$; let $i:=1$, then repeat the following:
Mark room $V_i$ with $N$.
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$.
If all vertices are marked $N$, done. Otherwise, let $i:=i+1$ and return to Step 2.

Observations

Any winning strategy prepended with arbitrarily many moves will still be a winning strategy.
If there exists a pair of moves $(V_i,V_j), i \lt j,$ such that the state of the graph on night $i$ is the same as that on night $j$, then moves $V_{i+1}, \dots, V_j$ are redundant.

Step 4

Be excellent and solve the problem

An algorithm to find which room to pick

Mark all rooms with $Y$.
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.
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)$.

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

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

Which graphs are solvable?

Any graph containing a cycle is not solvable. (only trees are solvable)
This tree is unsolvable:

Any graph containing that tree is unsolvable.
Every other tree is solvable.

Thanks!

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