Combinatoric Problem in Stardew Valley about Keg Layout

Question

I will first give the mathmatical description of the problem, which I think is a good problem for high school MOers.

Given positive integers $m, n \geq 3$, where $m$ is an odd number, consider a rectangle with $m$ columns and $n$ rows, divided into $mn$ small $1 \times 1$ squares. A good coloring of this rectangle is to color each small square with either black or white, with the following conditions held:

• All the white squares are connected.
• For each black square, one of the squares who share at least a common vertex (so it could be adjacent horizontally, vertically or diagonally) is white;
• The middle square on the bottom is white.

Among all possible good coloring, find the minimum number of white squares.

I guess the answer depends on the $m,n$ modulo 3. I know when $m=n=5$, the answer should be 8. However, I cannot find a prove that can be generalized for all $m, n$.

Background for this problem: This is a problem about the best keg layout in Stardew Valley, a fantastic Steam game. You want to place as many kegs(black squares) in a room of shape $mn$ as you can, but the same time leave a path(white squares) for your movement. You can operate the keg if it is adjacent to you horizontally, vertically or diagonally. We color the midpoint of the bottom white because after all we need a door for this house. According to Stardew Valley wiki, when $m = 11, n = 9$, the answer should be 32 (with 67 kegs), and when $m = 17, n = 12$ the answer should be 67 (with 137 kegs).

The following are considered optimal for case $m = 11, n = 9$ and $m = 17, n = 12$ by Stardew Valley players.

Answer 1

For a proof for the $n$ is a multiple of $3$ case, consider growing the network of white spaces one square at a time. Each new white square can make at most $3$ new squares accessible (with the exception of the original square) because the other $6$ were already accessible from the previous white square that you reached it from. Therefore to add $3k$ accessible squares (black or white) requires adding at least $k$ white squares.

We start our network with one white square rendering $6$ squares accessible, so to cover $mn$ squares we need to add an extra $ mn-6$ squares, requiring an extra $\frac13 mn-2$ white squares, for a total of $\frac13 mn-1$. The arrangement shown achieves this bound, so is optimal.

This provides a lower bound of $\lceil \frac13 mn\rceil-1$ white squares regardless of $m$ and $n$, and this is always be attainable.

---

Actually I also need to show every square is accessible in an optimal arrangement: this is easy because if there are inaccessible squares, some must border the accessible region, meaning there is a square that can be made accessible with only one white square (i.e. net $0$ black squares). By doing this repeatedly we find an arrangement where every square is accessible with has at least as high a capacity.

Answer 2

I will generalize your problem somewhat. Define the "threshold" of a house to be the floor square which is adjacent to the door. You specified that the threshold should be in the middle of the bottom row; I will give a strategy that works when the threshold is any edge square (except for a corner).

Theorem: For a house with $m$ rows and $n$ columns, the fewest number of white squares in a successful keg placement is $\lceil \tfrac13mn\rceil-1$.

Proof: Assume, without loss of generality, that the threshold is on the south wall or the west wall.

I will illustrate the strategy in several cases, based on the remainders of $m$ and $n$ modulo $3$. Furthermore, I will only show one example case, and hope that the generalization to larger $m$ and $n$ is apparent. Every possibility is covered below, though you might need to diagonally reflect your room, switching $m$ and $n$, to find the matching case. Note that the threshold square is not illustrated; you can delete any non-corner keg on the south wall or west wall and make it the threshold.

The fact that these arrangements are optimal follows from Zoe Allen's answer. More directly, you can see that as you add the white squares one at a time in these arrangements, you are always making exactly three new squares "accessible", in Zoe's language. Since Zoe's proof shows that you can make at most three new squares accessible each time, these are optimal.

Case A: One of the dimensions is a multiple of three.

 # # # # # # #
 # . . . . . #
 # . # # # # #
 # . # # # # #
 # . . . . . #
 # . # # # # #
 # . # # # # #
 # . . . . . #
 # # # # # # #

Case B: $m\equiv 1\pmod 3$, $n\equiv 1\pmod 3$.

 # # # # # # # # # # 
 # . # # . # # . . #
 # . . . . . . . . #
 # . # # # # # # # #
 # . # # # # # # # #
 # . . . . . . . . #
 # . # # # # # # # #
 # . # # # # # # # #
 # . . . . . . . . #
 # # # # # # # # # #

Case C: $m\equiv 1\pmod 3$, $n\equiv 2\pmod 3$.

 # # # # # # # # # # #  
 # . # # . # # . # . #
 # . . . . . . . . . #
 # . # # # # # # # # #
 # . # # # # # # # # #
 # . . . . . . . . . #
 # . # # # # # # # # #
 # . # # # # # # # # #
 # . . . . . . . . . #
 # # # # # # # # # # #

Case D: $m\equiv 2\pmod 3$, $n\equiv 2\pmod 3$.

 # # # # # # # # # # #
 # . # # . # # . . . #  
 # . # # . # # . # # #
 # . . . . . . . . . #
 # . # # # # # # # # #
 # . # # # # # # # # #
 # . . . . . . . . . #
 # . # # # # # # # # #
 # . # # # # # # # # #
 # . . . . . . . . . #
 # # # # # # # # # # #

Answer 3

The easy case is the ones you have shown, when $n$ is a multiple of $3$. You have $\frac n3$ rows with aisles, each with $m-2$ white squares. The other rows except the top one just have one white square in the middle, so you have $\frac n3(m-2)+\frac {2n}3-1=\frac {mn}3-1$ white squares. This agrees with the diagrams you give.

When $n$ is one less than a multiple of $3$ I don't see how you do better than removing the bottom row from one of your pictures. You now have $\frac {n+1}3$ aisles with $m-2$ squares and $\frac {2n-2}3$ more squares in the center aisle for $\frac {n+1}3(m-2)+\frac {2n-2}3$ white squares.

When $n$ is one more than a multiple of $3$ it is very frustrating. You have to remove another almost full row.

All this assumes that $m$ is sufficiently greater than $n$. If $n$ is enough greater than $m$ it becomes better to make vertical aisles instead of horizontal ones. I leave it to you to think about that and the crossover point. Now the easy case is when $m$ is a multiple of $3$.