The Door Problem and a Mold Game

This blog has not yet been peer reviewed. Some things may be incorrect.

Yesterday, I witnessed and fell victim to a slew of assassination attempts. It was brutal, bloody, and horrifying.

xkcd nerd sniping:
XKCD 356
I'll unpack the murder weapon (the problem), show my solution, and try to expand and generalize the result.

The Door Problem

The problem is as follows:

Amelia is hiding behind one of five doors. You can open a door, look to see if she's there, and then close the door. After you close the door, she will move one door to the left or one door to the right. How can you guarantee you will always find her? And what is the minimum number of doors you need to open to do so?

So, you need to find an algorithm that will always eventually find her, even in the worst case.

five doors in a line

Perhaps one way to solve this is to look closely at one door. Like, really closely. Close enough to see the mold growing on the top of it. Gross.

Moldy Doors

The green mold begins at a layer on the top of the door. This is a special kind of mold, though. It aims to grow downwards, but only so diagonally. Your goal is to stop the mold from growing, and lucky for you, you never forget your special blue tape. You know, the type of tape that mold can't grow on. But you're limited in how you can place it — you can only place one piece of blue tape on the layer of most recent growth. A turn consists of

  1. You place one piece of tape on the bottom-most layer containing mold.
  2. The mold grows diagonally downwards. That is, a square on the next layer is turned to mold if it has a diagonally-adjacent tile with mold.
You win if mold cannot grow any further.

To start, place a piece of tape on the topmost layer. (works best on desktop)
refresh page to reset board
A Solution
a solution for the mold game at 5 tiles wide, or a solution to the door problem with 5 doors

The Connection

How does the mold game connect to the door problem? Well, we can think of each row of tiles in the mold game as a turn in the door problem, and think of each tile as a door. Then, a moldy tile corresponds to a door Amelia can be behind. Placing our blue tape is analogous to opening a door. Notice that the empty tiles are doors we know she can't be behind, and thus our goal is to eventually make a row of all empty tiles.

Using this connection, our goal can be restated as finding solutions to this mold game. For a width of five tiles (five doors), the optimal solution seems to be 6.

This game helps us keep track of the door problem on a large number of doors:

refresh page to reset board
A Solution
a solution for the mold game at 17 tiles wide, or a solution to the door problem with 17 doors

If one follows the solutions I've given, there is an upper bound for optimal solutions. Namely, for \(n \geq 3\) doors, you can find a solution with only \((n - 2) * 2\) moves. This seems optimal, as in the upper bound is equal to the optimal score, but I'm lazy and don't want to prove this. Consider it a proof by not being able to think of a counterexample (flawless logic). Instead, we can see what this game says about more general versions of the door problem.

Generalizing to Any Graph

In the door problem, we have five doors in a single line. If we think of each door as a vertex in a graph and each connection between the doors which Amelia can travel to on her turn as edges, then we simply have a path graph with five vertices.

doors as a 5 path graph

It's natural here to extend this problem to any (simple, connected) graph. For example, we can consider the door problem on the cyclic graph \(C_5\). That is, if Amelia is behind the leftmost door, she can move to the rightmost door on her tern, and vice versa.

doors as a 5 cycle graph

Well, this is just our mold game but the mold is allowed to grow diagonally down at the edges and appear on the other side.

refresh page to reset board

We can see that the information we were able to get before (information, here, being the empty tiles—knowing where she's not) isn't obtainable now. Before, we were able to get a tile of information (a blank tile) and build off of it, in a sense, until we had a whole row of blank tiles. Here, we can't even get started. The takeaway: the door problem is impossible on a cyclic set of doors.

I want to show now that if a graph contains a cycle, the door problem is unsolvable on it. Doing this is hard with the mold game, since we're limited to a two-dimensional visualization. One way to formalize this instead is to consider the strong product \(G \boxtimes P_n\) where \(G\) is the graph we're playing on and \(P_n\) is a path of length \(n\), where \(n\) is greater than or equal to the minimum number of turns we need. Label the vertices of \(P_n\) with \(1,\dots,n\).

The vertices \((v, 1)\) for all \(v \in G\) start out colored green (moldy). Let \(t\) be the turn, starting at \(t = 1\). Then, a turn is performed as

  1. Color a vertex \((v, t)\) blue.
  2. Color all vertices \((w, t + 1)\) green if and only if \((w, t+1)\) is adjacent to some green \((x, t)\) where \(w \neq x\).
  3. Increment \(t\) by 1.
We want to know for which graphs \(G\) there exists an \(n\) such that \(G \boxtimes P_n\) terminates on some choice of moves under the above rules.

Notice how this game works on our original problem of 5 doors using the strong product \(P_5 \boxtimes P_6 \), switching out tiles for vertices:

strong product of P5 and P6

Also note that using this strong product model shows that cycles are impossible for this game.

strong product of C3 and Pn doesn't work
\(C_3 \boxtimes P_n\) can't gain information; the mold keeps growing
This works in the general case \(C_k\) as well.

Here's the thing: if \(C_k\) is a cycle graph of \(k\) vertices and a graph \(G\) contains \(C_k\) as a subgraph, then \(G \boxtimes P_n\) contains \(C_k \boxtimes P_n\) as a subgraph. Thus the mold game on \(G \boxtimes P_n\) shouldn't terminate for any \(n\), since mold will keep growing on the subgraph \(C_k \boxtimes P_n\). We conclude that the mold game can't terminate on a graph containing a cycle. Hence, the door problem is only solvable on acyclic graphs. Since we really only care about connected, finite graphs, we can say further that the door problem is only solvable on trees.

It seems like not all trees will work. All paths work, as we've seen. But it's hard to see whether the door problem is solvable on certain trees.

some tree
Does the door problem terminate on this tree?
We've yet to show anything rigorously, so there is of course room for error in this. But it seems as though the door problem is equivalent to the mold game, which showed us that the door problem is only solvable on acyclic graphs. Which is pretty cool :)