Problem 6

Here is an explicit construction, not just a picture. Number rows and columns from $1$ to $n$, put $n=k^2$, and leave black the cell $B_r=(r,\;k((r-1)\bmod k)+k-\lfloor(r-1)/k\rfloor)$ for each $1\le r\le n$. For every $0\le p,q\le k-2$, place one $k\times k$ square tile $T_{p,q}$ whose row interval is $[2+kp+q,\,1+k+kp+q]$ and whose column interval is $[k-p+kq,\,2k-1-p+kq]$. The remaining boundary rectangles are these: for $1\le q\le k-1$, rows $[1,q]$ and columns $[kq+1,k(q+1)]$; for $0\le p\le k-2$, rows $[kp+1,k(p+1)]$ and columns $[1,k-1-p]$; for $1\le p\le k-1$, rows $[kp+1,k(p+1)]$ and columns $[k^2-p+1,k^2]$; for $0\le q\le k-3$, rows $[k^2-k+2+q,k^2-1]$ and columns $[kq+1,k(q+1)]$; and one last rectangle in row $k^2$ and columns $[1,k^2-k]$. Each displayed interval is nonempty in its stated range. The black-cell formula has one cell in every row and column. A direct interval check shows that the $k\times k$ tiles and these boundary rectangles are pairwise disjoint, avoid every $B_r$, and cover every other cell: the four families fill respectively the top, left, right, and bottom gaps around the $(k-1)\times(k-1)$ array of square tiles. There are $(k-1)^2$ square tiles and $(k-1)+(k-1)+(k-1)+(k-2+1)=4(k-1)$ boundary tiles, hence $(k-1)^2+4(k-1)=k^2+2k-3$ tiles.