\documentclass[11pt]{scrartcl}
\usepackage{evan}
\begin{document}
\title{Twitch 091.2}
\subtitle{Evan Chen}
\author{Twitch Solves ISL}
\date{Episode 91}
\maketitle
\section*{Problem}
Suppose there are $N$ blocks with dimensions $1 \times 2 \times 4$
which are placed in an axis-aligned way in a
$(2n+1) \times (2n+1) \times (2n+1)$ cube.
(The blocks may be rotated.)
Prove that if $n \equiv 1 \pmod 4$ or $n \equiv 2 \pmod 4$ then
\[ N \le \frac{n (n+1)(2n+1)}{2} - 1. \]
\section*{Video}
\href{https://www.youtube.com/watch?v=xrAkxr6mB9w&list=PLi6h8GM1FA6yHh4gDk_ZYezmncU1EJUmZ}{\texttt{https://youtu.be/xrAkxr6mB9w}}
\newpage
\section*{Solution}
Call a $1 \times 2 \times 4$ block an \emph{ice tray}.
First, note that in every
$(2n+1) \times (2n+1) \times 1$ cross section,
any ice tray intersects the cross section in an even number of cells.
This immediately implies there are $2n+1$ cells not in an ice tray,
giving a bound of
\[ N \le \frac{(2n+1)^3-(2n+1)}{8} \]
which is one more than the requested bound.
So we have to show this is not always sharp.
Impose coordinates $\{0,1,\dots,2n\}^3$.
Assume for contradiction there is an equality case above
and let $S$ be the coordinates of those $2n+1$ \emph{missing} cells.
We also will say a missing cell is \emph{even} or \emph{odd}
according to the parity of the sum of its coordinates.
Then consider the generating function
\[ F(X) = (X^0+X^1+\dots+X^{2n})^3
- \sum_{(a,b,c) \in S} X^{a+b+c}. \]
This is the sum of $X^{\text{sum coords}}$ over all cells.
Because the cube was partitioned into ice trays,
it follows that that $F$ is divisible by $(1+X)(1+X+X^2+X^3)$,
as this polynomial divides the contribution of any ice tray.
In particular, if $n \equiv 1 \pmod 4$ then
\begin{align*}
0 = F(-1) &= 1 - \sum_{(a,b,c)} (-1)^{a+b+c} \\
0 = F(i) &= 1 - \sum_{(a,b,c)} i^{a+b+c}.
\end{align*}
The first equation implies there are $n+1$ even missing cells,
and $n$ odd missing cells.
But then the second equation is not possible,
because the real component of the sum should have the
same parity as $n+1$.
Similarly, if $n \equiv 2 \pmod 4$ then
\begin{align*}
0 = F(-1) &= 1 - \sum_{(a,b,c)} (-1)^{a+b+c} \\
0 = F(i) &= i - \sum_{(a,b,c)} i^{a+b+c}.
\end{align*}
The first equation implies there are $n+1$ even missing cells,
and $n$ odd missing cells.
But then the second equation is not possible,
because the real component of the sum should have the
same parity as $n+1$.
\end{document}