An $n$-stick is a $1×n$ or $n×1$ tile. Let $P$ be a lattice polygon (whose edges are parellel to either the $x$-axis or the $y$-axis) which can be completely tiled only with $n$-sticks for a given positive integer $n$, without allowing any overlaps. $C(P, n, k)$ is the number of 'bottom left vertices of n-sticks that tile $P$' on the line $x + y = k$, where $k$ is an integer. Does every $P$ satisfy the following for any $n$ and $k$?:
$C(P, n, k)$ stays constant regardless of how $P$ is tiled.
Yes. Without loss of generality, we’ll consider polyominoes here, which are connected shapes formed via the union of grid aligned squares. (Non integer offsets just break this problem into disjoint copies of the polyomino case.)
Sort each cell by the sum of its coordinates. We prove the result by induction. Obviously the most “southwest” layer will have a constant value of $C$, namely the number of cells in that diagonal row. For each subsequent layer, we add up the number of corners of sticks in the previous $n-1$ layers to get a total $t$ - this is the number of cells which are already occupied in our tiling from previously placed sticks. Then subtracting $t$ from the number of cells in our current diagonal tells us the number of new sticks we need to add whose southwest corners fall in the current diagonal, thereby fixing our value of $C$.
Since we only took as input the number of cells in each diagonal, this computation must be invariant under and valid choice of tile placements.
This same argument can be used to provide an alternate solution to the classic chessboard problem - by computing $C$ along each diagonal, one eventually obtains a negative value and thus a contradiction with the assumption that a tiling existed.