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.

View MathsJams current and potential in a larger map

- 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

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?

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

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.

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

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

- If that state has been seen before, ignore and return
- Of the rooms looked at in Step 2 which didn't return
`null`

, return the one with the shortest strategy.

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.

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

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

/

#