4

The question Square Fencing [combinatorics] was put on hold because what was being asked was unclear.

However, some progress had been made, especially by @MikeEarnest, and some very clear questions can be asked about the situation. Here is one such question, together with a rough solution which people might be interested to improve/extend.

In the picture below:

$4$ black squares surround $1$ white square

$7$ black squares surround $3$ white squares.

https://i.stack.imgur.com/4xJDW.jpg

Prove that $4n$ black squares can surround at most $2n^2-2n+1$ white squares.

Consider an arrangement for which the number of white squares is maximal. Assume the white squares are in solid rows of squares. Let there be $c$ white squares in the longest row and let there be $k+l+1$ rows.

In order from top to bottom let the numbers of squares in the top $k+1$ rows be $$a,a+e_1,a+e_1+e_2, ... , a+e_1+e_2+...+e_k=c.$$ In order from bottom to top let the numbers of squares in the bottom $l+1$ rows be $$b,b+f_1,b+f_1+f_2, ... , b+f_1+f_2+...+f_l=c.$$ It would need proving, but it does seem self-evident that each $e_i$ and $f_i$ is non-negative because, if not, we could adjust the arrangement to enclose at least no fewer white squares.

Each white square has 4 boundary edges which must join it to either another white square or a black square. The two ends of each row require $2(k+l+1)$ black squares. Now consider, say, the third row which contains $a+e_1+e_2$ squares. Its upper edges will need to be joined to $e_2$ black squares at most two of which could already have been counted at the ends of the second row. Furthermore, if $e_2>2,$ then an extra white square can be put at one or other end of the second row without requiring any extra black squares.

In general, we can suppose that all of $a,b,e_i,f_i$ are at most $2$. The total number of black squares which are required is therefore $$2(k+l+1)+a+b.$$ Without loss of generality suppose that $a+2k\ge b+2l$.

As we have seen, without increasing the number of black squares, the numbers of squares in the rows can be increased (or at least kept the same) to $$a,a+2,a+4, ... , a+2k,a+2k-2, ..., a+2(k-l).$$ Also, as noted earlier we could increase the number of white squares if either $a$ or $b$ was greater than 2. We can therefore suppose $a=b$ is either $1$ or $2$ and so $k=l$.

For $4n$ black squares we now have the type of arrangement noted by @MikeEarnest.

$a=b=1$ and $n=k+1$. The number of white squares is $n^2+(n-1)^2=2n^2-2n+1$.

Extra result

For $4n+2$ black squares the same arrangement but with $a=b=2$ and $n=k+1$ has $2n^2$ white squares.

0 Answers0