A stick is defined as a $1 \times k$ or $k \times 1$ rectangle for any integer $k \geq 1$. We wish to partition the cells of a $2022 \times 2022$ chessboard into $m$ non-overlapping sticks, such that any two of these $m$ sticks share at most one unit of perimeter. Determine the smallest $m$ for which this is possible.
§3.1a Solution
In general, with 2022 replaced by $n$, we will prove the answer is
$$
m=\left\{\begin{array}{ll}
1 & \text { if } n=1 \\
3 & \text { if } n=2 \\
\frac{1}{2}\left(n^{2}-2 n+7\right) & \text { if } n \geq 3 \text { and } n \text { is odd } \\
\frac{1}{2}\left(n^{2}-2 n+8\right) & \text { if } n \geq 3 \text { and } n \text { is even, }
\end{array}\right.
$$
with the following construction. For $n=2022$ this gives 2042224 as the answer.
The optimality for $n \in\{1,2\}$ is easy to check, so assume $n \geq 3$.
The main idea is to view the problem as taking an $n \times n$ grid of squares and deleting some of the edges until the resulting figure is a set of sticks. Since the number of sticks is equal to $n^{2}$ minus the number of removed edges in the square, it suffices to maximize the number of removed edges. However:
Claim - No two of the deleted edges may share an endpoint.

Proof. Obvious.
As a consequence of this claim:
- At most $\frac{1}{2}(n-3)^{2}$ edges can be removed within the central $n-3$ by $n-3$ grid of lattice points.
- Additionally, at most $4(n-2)$ of the outer edges can be removed since there are $4(n-2)$ lattice points within one unit of the boundary.

Hence, the minimum number of removed edges is at least
$$
n^{2}-\left(\left\lfloor\frac{1}{2}(n-3)^{2}\right\rfloor+4(n-2)\right)
$$
which equals the claimed minimum.
Remark (Torus variant). One can ask the same problem on an $n \times n$ torus. The answer is $\frac{1}{2} n^{2}$ for even $n$ and $\frac{1}{2}\left(n^{2}-1\right)$ for odd $n$; the proof is analogous to the one above, but without the outer edge consideration.