How much warehouse space can we use so that all the crates are accessible?

Question

The warehouse has a square floor with a side of 12 m, divided into 144 squares with a side of 1 m. In each 1 m square can be placed a crate, filling up the square entirely. All the crates have to placed perfectly in lines. You cannot put the crate in the lower right corner, because there is the only door to the warehouse. Each crate must be accesible from at least one side. We move around the warehouse by walking on empty squares, moving from a square to the adjacent square.

• (a) How many boxes can we store (according to the rules above) in the warehouse? Show a solution.
• (b) Find a maximum solution to (a) using n crates and prove we cannot store n + 1 crates.

Here are some examples to help.

Pretty good idea is to use the bottom row for a walkway and then store crates in every second column. Even better idea is to use the leftmost column entirely (even the bottom tile) and then leave one empty column, use two columns, then one gap and so on... This gives 89 used squares if I am right. All the restrictions I can think of are pretty weak e.g. an empty tile is adjacent to no more than 4 used tiles so at least 1/5 tiles are empty.

Answer 1

Here's a solution with $91$ crates:

X XX XX XX X
X XX XX XX X
X XX XX XX X
X XX XX XX X
X XX XX XX X
X XX XX XX X
X XX XX XX X
X XX XX XX X
X XX XX XX X
X XX XX XX X
X
X XXXXXXXXX.

I can prove that at most $96$ crates are possible.

Suppose that there are $x$ crates and $y$ empty squares we can reach from the start; possibly, there are also some inaccessible empty squares, so $x+y \le 144$. In any arrangement, it is possible to give each square except for the entrance a "parent square" such that:

• every parent is an empty space;
• by starting at any crate and repeatedly going to the parent square, we eventually get to the door of the warehouse.

Excluding the entrance entrance, there are $x+y-1$ squares that must have a parent. However, each of the $y$ accessible empty squares can only be a parent three times, so $x+y-1 \le 3y$, or $x-2y \le 1$. Therefore $3x = 2(x+y) + (x-2y) \le 2(144)+1 = 289$, which means $x \le \frac{289}{3}$. Because $x$ is an integer, we conclude $x \le 96$.

In the solution above, we get fewer crates due to $7$ empty spaces next to a wall (these are inefficient because they can only be a parent twice) and $9$ crates with two adjacent empty spaces (these are inefficient because they get two parents). With these inefficiencies in play, we actually know $x \le \frac{289 - 7 - 9}{3} = 91$.

It's possible that we can have fewer than $7+9$ inefficiencies. (We can't eliminate inefficiencies entirely; for example, the entrance is an empty space next to a wall, which is already $1$ inefficiency). Proving a lower bound bound on the number of inefficiencies probably requires tedious casework.