Partitioning a set of lattice points in the plane into rectangles

Question

The "long comment" by Pietro Majer on Reference for puzzle on dividing piles and scoring products suggests the following problem. Let $S$ be a finite subset of $\mathbb{Z}\times \mathbb{Z}$. By a rectangle, I mean an $a\times b$ array of contiguous elements of $\mathbb{Z}\times \mathbb{Z}$ ($a,b\geq 1$). E.g., $\{(0,0),(2,0)\}$ is not a rectangle since $(1,0)$ is missing.

1. Let $\nu(S)$ be the greatest number of elements of $S$ such that no two lie in a rectangle contained in $S$. Let $\rho(S)$ be the least number of disjoint rectangles whose union is $S$. For what $S$ do we have $\nu(S)=\rho(S)$? Clearly $\nu(S)\leq \rho(S)$.

2. Suppose we remove a maximal rectangle $R$ from $S$, then a maximal rectangle $R'$ from $S-R$, etc., until after $k$ steps we have removed all the elements of $S$. For what $S$ do we have that $k=\rho(S)$ (for any choice of $R,R',\dotsc$)?

These questions can easily be extended to higher dimensions.

Answer 1

Here is a generalization of the original puzzle that also satisfies conditions (1) and (2). Let $k, \ell,n \in \mathbb{N}$, and $S$ be the set of lattice points contained in the convex hull of $\{(-\ell, 0) , (-\ell, n), (0,n), (nk, 0)\}$. Note that the original puzzle corresponds to the case that $\ell=0$ and $k=1$. I claim that $S$ also satisfies (1) and (2).

For (1), note that $S$ can be partitioned into $n+1$ disjoint rectangles (take maximal horizontal line segments, for example). On the other hand, let $S':=\{(0,n), (k,n-1), (2k, n-2), \dots, (nk, 0)\} \subseteq S$. Since no two points in $S'$ can be covered by the same rectangle, we have $\nu(S)=\rho(S)=n+1$.

For (2), note that removing any maximal rectangle from $S$ yields two smaller instances $S_1$ and $S_2$ of the same problem, such that the sum of the 'heights' of $S_1$ and $S_2$ is one less than the height of $S$. Thus, any sequence of rectangles chosen by the procedure given in (2) will terminate after exactly $n+1$ steps.

Note that not all subsets of $\mathbb{Z} \times \mathbb{Z}$ satisfy (1) and (2). In fact, we claim that the set $S=([3] \times [6]) \setminus \{(1,3), (1,6), (3,1), (3,4)\}$ fails both (1) and (2).

For (1), it is easy to check that $\rho(S)=5$, but $\nu(S)=4$.

For (2), if we choose $R=\{(1,4), (1,5), (2,4),(2,5)\}$ as the first maximal rectangle to remove, then procedure (2) will produce a partition of $S$ into six rectangles. However, as already noted, $\rho(S)=5$.