Partitioning a set of lattice points in the plane into rectangles 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.

*

*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)$.


*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.
 A: 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$.
