What is the maximum amount of "shore" tiles in a rectangular grid that has only "water" and "land" tiles?

Question

I'm not a mathematician or anything of the like, so please forgive me if I'm not using the correct terminology for something.

The problem is as follows:

Given a rectangular grid that has $m*n$ tiles, where $m$ is the amount of rows and $n$ is the amount of columns in the grid, and knowing that:

• $1 \leq m \leq 100$
• $1 \leq n \leq 100$
• Every tile is classified as either water or land
• The grid can have any amount of water tiles ranging from $0$ to $m*n$
• A shore tile is defined as any land tile that has at least 1 of its 4 (or 3 on the edges, or 2 on the corners) adjacent tiles as a water tile

What is the maximum amount of shore tiles a grid can have (I'll call it $R$)?

I started working on this by first trying to solve for very small grids and go up from there, so, for a 1x1 grid, $R = 0$, since there can't be any adjacent tile to that single tile.

W: water tile
L: land tile
$s$: amount of shore tiles

Then, for 1x2 grids:

WW	WL	LL
$s=0$	$s=1$	$s=0$

So, for 1x2 (and 2x1) grids, $R = 1$

For 1x3 grids:

WWW	WWL
$s=0$	$s=1$

(ignoring some other possibilities with 1 L, because I'm interested in the maximum value, and $s$ can't be higher than the amount of L in the grid)

WLL	LWL	LLL
$s=1$	$s=2$	$s=0$

So, for 1x3 (and 3x1) grids, $R = 2$

(...)

For 2x3 grids:

WWW WWW	WWW WWL	WWW WLL	WWW LLL	WWL LLL	LWL LWL	WLL LLL	LWL LLL	LLL LLL
$s$=0	$s$=1	$s$=2	$s$=3	$s$=3	$s$=4	$s$=2	$s$=3	$s$=0

(with only 2 rows or columns, $s \leq 3*\text{amount of W's}$, and reaching the maximum has been confirmed to be possible here)

So, for 2x3 (and 3x2) grids, $R = 4$

|m \ n|1|2|3|4|5|6|
|-----|-|-|-|-|-|-|
|  1  |0|1|2|2|3|4|
|  2  |1|2|4|?|?|?|
|  3  |2|4|?|?|?|?|
|  4  |2|?|?|?|?|?|
|  5  |3|?|?|?|?|?|
|  6  |4|?|?|?|?|?|

So, up until now $$R = m*n - 1 - \lfloor m*n/4 \rfloor$$ But this is likely not a general formula (right?).

Is there a known general solution for mxn grids? And if so, is there an easier way for getting to it than what I'm doing?

Edit: reduced amount of examples, tried to fix the table at the end.

Edit 2: since it seems like the preview and the actual table don't match, I'll leave the table preformatted for now.

Answer 1

$1\times n$: As every water can contribute to at most two shore tiles, we can have 2 shore tiles for every 3 tiles. If $n$ is not a multiple of 3, the remainder can give us at most one additional shore tile, namely by “LW” if $n\bmod 3=2$. All in all, we find $R=\lfloor\frac{n+1}3\rfloor+\lfloor \frac n3\rfloor\approx \frac23 mn$ and this cannot be beaten.

$2\times n$: Now, every water can contribute to at most three shore tiles. Repeating LWLL in the first and LLLW in the second row, we end up with almost all these L being shore - except the first L in the second row and perhaps the last L in at most one of the rows. I leave the details to the reader, but we end up with $R\approx\frac34 mn$ with a small bound on the error

$m\times n$: When not everything is boundary, a single water can supply four shore tiles in a plus shape. These plus shape can tile the plane such that in the limit, the optimal value $R\approx \frac 45mn$ can be achieved. The situation at the boundary is a bit more complex, the error is but much less than the length $2n+2m-4$ Of the boundary. Concretely, if for $1\le i\le n$, $1\le j\le m$, we place water off $2i+j\equiv 0\pmod5$, then we “lose” quite exactly $\frac15$ of area to water - in fact exactly one fifth on any $5\times x$ or $x\times 5$ rectangle, so the details depend only on the lower right $n\bmod 5$ by $m\bmod 5$ rectangle, for which shape we may check that at most one more water tile than one fifth of the area is used. Thus we have $\lceil \frac15mn\rceil$ water tiles. Moreover, only $\lfloor \frac n5\rfloor$ of the tiles in the top row are non-shore land, similarly $\lfloor \frac m5\rfloor$ for the leftmost column. The situation at the bottom row and rightmost column may be worse, but can be bounded as $\lceil \frac n5\rceil$ and $\lceil \frac m5\rceil$, respectively. You are invited to combine these estimates into a single formula - it will be something like $\frac 15(2n-1)(2n-1)+O(1)$. A marginally better solution may exist for some cases, but I highly doubt it.

Answer 2

Let us present on examples a graphical understanding of how sub-optimal solutions can be constructed. This looks to be in the same 'spirit' as the answer given by @Hagen von Eitzen:

Fig. 1: Case $m=10, n=7$. Yellow: sand, Blue: water (of course...). The land, if any, is brown. Not yet optimal (see Fig. 2)...

Fig. 2: Looks good... but is still far from optimality.

With width-2 sand strips with a 45° slope, separated by width-1 water strips as displayed on Fig. 2, we have 46 yellow "tiles" for a total of $70$, with an approximate proportion $\approx 0.66\%$.

One can in fact get better arrangements as remarked by @Tanner Swett by placing the water tiles in a "quincunx" way (think to "knight's moves") like the one of figure 3, necessitating small adjustments at the boundary. This possibility comes from the paving of an infinite plane by greek crosses (the "plus" shapes of the answer by HvE, which are the "influence zone" of a water tile) as shown on fig. 4 where the places where adjustments have to be made are indicated by red crosses.

Fig. 3: Case $m=13, n=11$. Here, $106$ yellow tiles among $143$, otherwise said $\approx 74\%$ of the total number of tiles. Most horizontal strips display a "trend" of 4 yellow tiles among $5$; therefore, the density of yellow tiles will asymptotically be $80\%$ of the total number of tiles as explained in the solution by HvE.

Fig. Tiling of a rectangle (red boundary) with greek crosses.

Answer 3

I think it may need cases where "edge effects" come into play accounting for as special cases.

For 1xn a water tile can create 2 shore tiles, so you have an "optimal" ratio of 1:2.

For 2xn it is 1:5

For anything larger you are into 1:8.

Then every land tile can be a shore tile, and is equal to (total tiles) - (water tiles).

Depending on whether the minimum dimension is 1, 2 or 3+ divide total tiles by 3, 6 or 9 respectively, round up to next integer and that is the number of water tiles.