, 2020

For all $n$, the only possible value of $k(W_n)$ is $k = n + 1$.

By mathematical induction, it is easy to see that $W_n$ divides the plane into $C_2^{n+1} + 1$ regions. We convert this problem into a graph $G$, where each vertex corresponds to a region, and two regions that can be connected by a door are joined by an edge.

First, we prove that $k(W_n) \ge n + 1$. Note that the number of intersection points of the walls must be $C_2^n$, hence the number of edges of $G$ must be $C_2^n$. Let us first remove all edges from $G$, and then add them back one by one; each time we add back an edge, the number of connected regions in $G$ decreases by at most one, so the final number of connected regions of $G$ is at least $C_2^{n+1} + 1 - C_2^n = n + 1$. If we place one person in each connected region, then clearly these people can never meet, hence $k(W_n) \ge n + 1$.

Next, we prove that, regardless of what $W_n$ is, the following coloring method forces us to place at most $n + 1$ people:
- First, choose a rectangular coordinate system such that no wall is oriented north-south or east-west;
- Paint the west side of each wall green, and the east side blue.

Furthermore, we compute for each wall the eastward value $E$ = "the number of walls to the east of which this region lies". Clearly $E$ ranges between 0 and $n$, and for each value in this range there is exactly one region with "no wall to its north" corresponding to that $E$ value. Therefore, if we can prove:

**Claim. All regions with the same $E$ value are connected to each other.**

then we will have proven that at most $n + 1$ people can be placed, and thus the original proposition is established.

Proof of Claim.
Fix $i \in \{0, \dots, n\}$, and place a person in a region with $E = i$. Let this person move toward the north. Note that every bounded region is a convex polygon, and its northernmost edge must be an intersection point, which must have a door, so this person must eventually reach a region with no wall to its north. Furthermore, note that when a person passes through a door and arrives at a new region, exactly one wall switches from its east side to its west side, and exactly one wall switches from its west side to its east side, hence the $E$ value of all regions along this person's path are equal. Therefore, all regions with $E = i$ are connected to the region with no wall to its north and $E = i$, which completes the proof.