The Door Problem and a Mold Game

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

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.

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.

A Solution

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:

A Solution

If one follows the solutions I've given, there is an upper bound for optimal solutions. Namely, for $n\ge 3$ doors, you can find a solution with only $(n-2)\ast 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.

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.

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.

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⊠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\ne x$.
3. Increment $t$ by 1.

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

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

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⊠P_n$ contains $C_k⊠P_n$ as a subgraph. Thus the mold game on $G⊠P_n$ shouldn't terminate for any $n$, since mold will keep growing on the subgraph $C_k⊠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.