Skip to main content
2 of 3
Proof of optimality.
Victor Stafusa
  • 9.4k
  • 2
  • 33
  • 62

I got a solution with:

42 cells as hallways.

Here it is:

enter image description here


Proof of optimality

Suppose that instead of the hexagonal pattern, we had the 127 cells laid out as three lines with 42, 43 and 42 cells.

So what?

There, the 41 cells without communication to the exterior would necessarily be hallways, otherwise, either the hallway would be two or more disconnected sections or some cell would not be near a hallway. Plus some other exterior cell would also need to be a hallway in order to connect it to the exterior, making up a minimum of 42 hallways cells.

But duh! It is not a three line pattern, it is an hexagonal pattern!

As long as you can fit it the hallways, it doesn't matter. If you can't fit, it would just make things worse.

Taking the three line pattern, we could make the entire middle line, with the exception of one of the cells in the very end as hallways. We could also exchange the entrance for some cell in the other two lines. But in any way, there would be a cell that we should call as the "end-of-hallway cell" and a non-hallway cell covered by it that we should call as "the last room". Surely, if the hallway bifurcates (as it does), there would be multiple cells eligible for being entitled as such, but we can choose any one of the multiple candidates and the result is the same.

Most commonly, each hallway cell connect to other two hallway cells. Some hallway cells are bifurcations having three other hallway cells as neighbors and some are dead-ends, having only one. However, every time we add a bifurcation, we also add a dead-end since cycles are inherent suboptimal. Hallway cells with four or more neighbors also being hallways can't be optimal since this would only increase the density of hallway cells, which is what we want to decrease.

So, with the exception of the end-of-hallway cell and the entrance, this implies that in the optimal case, the average number of neighbors that are hallway cells to other hallway cells neighbors is exactly two. Further, disregarding only "the last room", exactly a third of the cells must be hallways, otherwise some room would be inaccessible.

We have 127 cells. One of them is "the last room", so we have 126 other cells. Get a third of that and we have 42. Hence, this is best possible.

Thanks to Kruga for the sketch of the proof in a comment.

Victor Stafusa
  • 9.4k
  • 2
  • 33
  • 62