Minimum area of an art gallery?

Question

I've adapted this problem from a TedEd riddle that I solved yesterday. It asks, what is the minimum number of rooms required such that every room except one room is connected to exactly three other rooms, except for one "special" room that is only connected to one other room. You can think of this like you're designing an art gallery to meet these conditions, and your "special" room contains a very rare painting which has to sit behind a vault door of which you only have one. I won't state the answer in this thread so as to not spoil the puzzle.

Anyway, I thought of an interesting extension of this puzzle. Suppose your building company is rather cheap, and can only build walls in integer multiples of one meter and walls can only intersect at right angles, i.e, they can only build on "gridlines". Note that non rectangular rooms are allowed, as long as any vertex has an interior angle of $90$ or $270$ degrees. Furthermore, a door takes up an entire one meter segment, and for ease of navigation, 2 rooms may not be touching without a door between them. My question is, what is the minimum area, in multiples of $1\text{m}^2$ boxes, of such a gallery design? How might I work this out?

Answer 1

Here's a proof of a lower bound of $10 \text{ m}^2$ if we want to replicate the $6$-room solution. Here's the graph:

Let's modify the gallery as follows. First, forget about the room adjacent only to one other room for now. Now four rooms have $3$ adjacencies, and one room only has $2$. Second, take the room with $2$ adjacencies, and break down one of the walls separating it from an adjacent room. Now we have only $4$ rooms left, and each one is adjacent to all the others.

As a graph, this graph has a unique planar embedding: three vertices in a triangle, and one vertex in the middle of the triangle. If we try to turn this planar embedding into an art gallery, then the room corresponding to the middle vertex has to be entirely surrounded by the other three rooms.

Even if the middle room is only $1\text{ m}^2$, it takes $8\text{ m}^2$ to completely surround it; making the middle room bigger would only hurt. That gives us $9\text{ m}^2$ of area already. We must have had the same area before we tore down a wall; if we put that wall back, the gallery still has to have $9\text{ m}^2$ of area.

Finally, this is all ignoring the room with $1$ adjacency, which adds another $1\text{ m}^2$ of area, for a total of $10\text{ m}^2$.

---

More generally, the argument above shows that if we want to go below $10\text{ m}^2$, then the graph of the art gallery with the vault room deleted must be outerplanar: there can't be a room entirely surrounded by other rooms.

However, an outerplanar graph can't have the degree sequence $3,3,3,\dots, 3,3,2$ (with any number of $3$'s, and only one $2$). The argument is a bit technical, but essentially, if all the vertices lie on a cycle, and we take any chord of the cycle, we are forced to put a degree-$2$ vertices somewhere on each side of the chord.

In other words, it's impossible to have an art gallery with the property in the question, if every non-vault room has to border the outside wall of the building.

Answer 2

Spoiler alert

If you're reading and you want to solve the TED problem, then quickly look away. I have hidden the diagrams & some key results to help reduce spoilers but it's too burdensome to hide all the text line by line.

Iteration 1

With problems like this, the best way to work is generally to do the following:

• Come up with bounds & prove that your bounds apply
• Share your results
• Challenge others to improve on your bounds

The result is either that the minimum is found, or a series of better and better bounds are found - if enough interested people join in the quest. Having said all that, here is a very simple start. I'm not offering much, mathematically, but hopefully will encourage others to make further contributions.

So, without further ado, here is an image of a solution to the problem (but not necessarily the minimal such solution):

Let $A$ be the minimum area of a gallery satisfying your constraints. From the above image, we know that the following upper bound applies to $A$:

$$A \leq 18$$

We also know, from the original puzzle, that there must be $6$ rooms, and each room must necessarily take up at least $1m^2$. So we know that:

$$6 \leq A$$

Therefore, we have bounds:

$$6 \leq A \leq 18$$

How might I work this out?

Well, now that you have bounds, the next steps are:

• Improve the bounds. In particular, I think there is a lot of low-hanging fruit on the lower bound .
• Write a computer program to brute force through the search space and see if it comes up with anything better than the above- for this, maybe just look for a single integer improvement of the upper bound. The bound is currently $18$, so just write a program that looks for a solutions using $17$ squares.

I hope others can join in the puzzle. I love these collaborative things.

Iteration 2

Assuming the "not touching" rule doesn't count single point intersections, the following is allowable as a solution:

Therefore we have a new upper bound of $10$. So:

$$6 \leq A \leq 10$$