Ishigami Does Not Want to See Couples

Next sort the rows by their numbers of colored cells in descending order. The number of horizontal boundary edges stays the same. The number of vertical boundary edges is the sum of the absolute differences between adjacent row counts. In any order, this sum is at least the difference between the largest and smallest counts. Descending order attains that difference, so sorting cannot increase the boundary length either.

Write the sorted row counts as $\ell_1\geq\ell_2\geq\cdots\geq\ell_N$, and let $q$ be the number of rows satisfying $0<\ell_i<N$. The boundary length is

Consider the following four cases.

• If $\ell_N=0$ and $\ell_1<N$, every nonempty row is partially colored. Hence $s\leq q\ell_1$, so $E=q+\ell_1\geq2\sqrt{s}$ and therefore $E\geq C_1$.
• If $\ell_N>0$ and $\ell_1=N$, swapping the colors and rotating the grid by $$ degrees reduces the arrangement to the preceding case. There are now colored cells, so .
• If $\ell_N=0$ and $\ell_1=N$, then $E=$. If , then is divisible by . Therefore, when is divisible by , and otherwise. In either case, .
• If $\ell_N>0$ and $\ell_1<N$, then every row is partially colored, so $q$. If , all row counts are equal and is divisible by . As in the preceding case, .

Every arrangement can be transformed into this form without increasing its boundary length. Consequently, every original arrangement also has boundary length at least $\min(C_1,C_2)$.

In the first construction, the height plus width of the colored shape equals $C_1$, and its row counts are nonincreasing. Its boundary length is therefore at most $C_1$. This bound remains valid if the shape touches the edge of the grid, removing some boundary edges.

In the second construction, the boundary length equals $C_2$ when $s\geq N$. When $0<s<N$, only part of the first row is colored, and the boundary length is $s+1\leq N+1=C_2$. Thus, this construction always has boundary length at most $C_2$.

Choosing the construction with the smaller bound gives a boundary length at most $\min(C_1,C_2)$, while the lower bound proves that every arrangement has at least this boundary length. The chosen arrangement is therefore optimal.