Return to Answer

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 (2). For example, let $S=\{(0,0), (0,1), (0,2), (0,3), (0,4), (1,0), (1,2), (1,4)\}$. If we choose $R=\{(0,2), (1,2)\}$ as the first rectangle to remove, then procedure (2) will produce a partition of $S$ into five rectangles. However, $S$ can be partitioned into four rectangles.

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

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.

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 (2). For example, let $S=\{(0,0), (0,1), (0,2), (0,3), (0,4), (1,0), (1,2), (1,4)\}$. If we choose $R=\{(0,2), (1,2)\}$ as the first rectangle to remove, then procedure (2) will produce a partition of $S$ into five rectangles. However, $S$ can be partitioned into four rectangles.

Here is a generalization of the original puzzle that also satisfies conditions (1) and (2). Choose $k, \ell,n \in \mathbb{N}$. Let $T$ be the triangle with vertices at $(0,0), (0,n)$, and $(kn, 0)$. Let $S$ be the set of lattice points $(x,y)$ contained in $T$; or with $ -\ell \leq x \leq 0$ and $0 \leq y \leq n$. 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 rectangles of 'height' $1$ 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.

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.