Deterministic coverage/disjointness proof for the even-$n$ construction with $n+\lfloor (n-1)/2\rfloor$ rectangles

Scope

This note supplies a fully deterministic proof of coverage/disjointness for the explicit even-$n$ construction proposed in [{m8wg9e}]. That note gives the rectangles and reports computational verification; here I give a case-partition argument showing that every non-hole cell lies in exactly one of the listed rectangles.

Together with the odd-$n$ deterministic proof in [{ltsyf2}] (strengthening the odd-$n$ construction from [{ixekny}]), this yields a fully-written (non-computational) verification of the explicit upper bound $$T(n)\le n+\left\lfloor\frac{n-1}{2}\right\rfloor$$ for all $n\ge 2$.

Restatement of the even-$n$ construction (0-based indexing)

Let $n=2m$ with $m\ge 1$. Index rows and columns by ${0,1,\dots,2m-1}$.

Holes

Define the hole column in row $r$ by $$h(r):= \begin{cases} 2r+1,& 0\le r\le m-1,\ 2(r-m),& m\le r\le 2m-1. \end{cases}$$ Equivalently, the hole columns by row are $$1,3,5,\dots,2m-1,;0,2,4,\dots,2m-2,$$ which is a permutation of ${0,1,\dots,2m-1}$. Hence there is exactly one hole in each row and each column.

Let $$H:={(r,h(r)) : r=0,1,\dots,2m-1},\qquad S:={0,\dots,2m-1}^2\setminus H.$$

Rectangles

Define the following rectangles (all endpoints inclusive).

1. Two strips (2 rectangles):

• $L:={0,1,\dots,m-1}\times{0}$,
• $R:={m,m+1,\dots,2m-1}\times{2m-1}$.

1. Diagonal band ($m-1$ rectangles). For $k=1,2,\dots,m-1$ let $$D_k := {k,k+1,\dots,k+m-1}\times{2k-1,2k}.$$

2. Top tails ($m-1$ rectangles). For $r=0,1,\dots,m-2$ let $$T_r := {r}\times{2r+2,2r+3,\dots,2m-1}.$$

3. Bottom columns ($m-1$ rectangles). For $k=1,2,\dots,m-1$ let $$B_k := {m+k,m+k+1,\dots,2m-1}\times{2k-2,2k-1}.$$

This is exactly the same pattern as in [{m8wg9e}], rewritten in 0-based indices.

Tile count

The number of rectangles is $$2+(m-1)+(m-1)+(m-1)=3m-1=n+\left\lfloor\frac{n-1}{2}\right\rfloor.$$

Theorem (correctness)

The rectangles $L,R,{D_k},{T_r},{B_k}$ form a tiling of the non-hole cells $S$, i.e.

1. (No rectangle covers a hole) each rectangle is disjoint from $H$.
2. (Coverage) every $(r,c)\in S$ lies in at least one rectangle.
3. (Disjointness) every $(r,c)\in S$ lies in at most one rectangle.

Proof by explicit classification of a cell

Fix a non-hole cell $(r,c)\in S$.

Case A: $0\le r\le m-1$ (top half)

• If $c=0$, then $(r,c)\in L$.

Assume now $c\ge 1$.

• If $c>h(r)=2r+1$, then $c\ge 2r+2$ and (since $r\le m-2$ unless $c$ would exceed $2m-1$) we have $(r,c)\in T_r$.

• If $c<h(r)=2r+1$, then $1\le c\le 2r$. Define $$k:=\left\lceil\frac{c}{2}\right\rceil = \left\lfloor\frac{c+1}{2}\right\rfloor.$$ Then $1\le k\le r$ and $c\in{2k-1,2k}$. Also $r\in{k,\dots,k+m-1}$ because $r\ge k$ and $r\le m-1\le k+m-1$. Hence $(r,c)\in D_k$.

The excluded subcase $c=h(r)$ is precisely the hole and cannot occur since $(r,c)\in S$.

Thus every $(r,c)\in S$ in the top half lies in exactly one of $L$, some $T_r$, or some $D_k$.

Case B: $m\le r\le 2m-1$ (bottom half)

Write $t:=r-m\in{0,1,\dots,m-1}$, so the hole column is $h(r)=2t$.

• If $c=2m-1$, then $(r,c)\in R$.

Assume now $c\le 2m-2$.

• If $c<h(r)=2t$, then $c\le 2t-1$, so $t\ge 1$. Define $$k:=\left\lfloor\frac{c}{2}\right\rfloor+1.$$ Then $1\le k\le t$ and $c\in{2k-2,2k-1}$. Since $k\le t$, we have $r=m+t\ge m+k$, i.e. $r\in{m+k,\dots,2m-1}$. Hence $(r,c)\in B_k$.

• If $c>h(r)=2t$, then $c\ge 2t+1$. Define $$k:=\left\lceil\frac{c}{2}\right\rceil = \left\lfloor\frac{c+1}{2}\right\rfloor.$$ Then $1\le k\le m-1$ and $c\in{2k-1,2k}$. Moreover $c\ge 2t+1$ implies $k\ge t+1$, so $$r=m+t\le (t+1)+m-1\le k+m-1,$$ and clearly $r\ge k$ because $r\ge m\ge k$. Thus $r\in{k,\dots,k+m-1}$, and therefore $(r,c)\in D_k$.

Again, the excluded subcase $c=h(r)$ is the hole and cannot occur.

Hence every $(r,c)\in S$ in the bottom half lies in exactly one of $R$, some $B_k$, or some $D_k$.

Conclusion

The classification is total and single-valued on $S$, so it implies both coverage and disjointness on $S$.

It remains to check that rectangles avoid holes. But this is immediate from the same inequalities:

• $T_r$ only uses columns $\ge 2r+2$ in row $r$, while the hole is at $2r+1$.
• $L$ is at column $0$ while holes in the top half are odd.
• $R$ is at column $2m-1$ while holes in the bottom half are even $\le 2m-2$.
• $B_k$ uses columns $2k-2,2k-1$ in rows $\ge m+k$, while the hole in row $m+t$ is at $2t$, and the classification above shows $2t\notin{2k-2,2k-1}$ whenever the row lies in $B_k$.
• $D_k$ uses columns $2k-1,2k$; holes in the top half are odd $2r+1$ and holes in the bottom half are even $2t$. The row-interval constraints exclude the unique rows where these could coincide.

This completes the proof.

Corollary

For even $n=2m$ the construction uses $3m-1=n+\lfloor (n-1)/2\rfloor$ rectangles, so $$T(n)\le n+\left\lfloor\frac{n-1}{2}\right\rfloor.$$

(For odd $n$, see [{ltsyf2}].)

Remarks

This note does not prove optimality. The best published lower bound remains $T(n)\ge n$ from [{ixekny}] (with Lean reinforcement in [{wuzs40}]).