Building a cube from small bricks such that no lines can be pushed through between the seams

I'm riffing on an old contest training question I jousted with 40 years ago.

The original problem was:

A solid $20\times20\times20$ cube is built out rectangular bricks of dimensions $2\times2\times1$. Prove that it is possible to "push" a line through the cube in such a way that the line is not obstructed by any of the bricks.

Solution: We need $2000$ bricks to build this cube. Imagine that the edges of the cube align with the coordinate axes, and that the cube is in the first octant with one of its vertices at the origin. So there are $19^2$ lines parallel to the $z$-axis going through the cube, each given by the equations $x=a, y=b, a,b\in\{1,2,\ldots,19\}$, lines parametrized by the choice of the pair $(a,b)$. Similarly, there are $19^2$ lines parallel to the $x$ and $y$-axes for a total of $3\cdot19^2$ lines. It turns out that one of these will go through the cube along the cracks between the bricks. The key observation is that each line will be blocked by an even number of bricks (spoiler hidden below in case you want to think about it yourself).

Take one of those lines, say $z$ arbitrary, $x=a$, $y=b$. Consider the two planes, the first defined by $x=a$ and the second by $y=b$. These two planes cut the cube into four parts, the volume of each is an even integer. Then consider how the bricks are split by these two planes. We see that a brick blocks this line if and only if its volume is split equally between the four parts – an odd contribution to each part. The claim follows.

As $2\cdot3\cdot19^2>2000$ it is impossible that all these lines would be blocked by two or more bricks. Therefore at least one of them is unobstructed, proving the claim.

Ok, that was the background story. On with the actual question.

As the size of the cube, call it $n$, grows, the number of bricks increases as $n^3/4$, but the number of those lines, call them integer lines, increases as a quadratic polynomial of $n$ only. Therefore sooner rather than later the above argument fails to work. In fact, this happens already with $n=22$ as $2\cdot3\cdot21^2<22^3/4$. The parameters $a,b$ obviously ranging from $1$ to $n-1$.

Is it possible to build a solid $22\times22\times22$ cube out of $2\times2\times1$ bricks in such a way that all the integer lines are blocked by at least one (hence at least two) bricks? If this is not possible with $n=22$, what is the smallest value of $n$ for which this construction is possible (if one exists)?

Given that the answer to my question is unknown, I will welcome answers explaining a construction for answerer's choice of $n$.

Consider the line determined by $(x,y)=(a,b)$ and the four regions into which the planes $x=a$ and $y=b$ slice our $2n\times 2n\times 2n$ cube. In particular, consider the number of unit cubes inside the diagonally opposite regions $x,y\leq a,b$ and $x,y\geq a,b$, which is $$2nab+2n(2n-a)(2n-b)\equiv 0\bmod 4.$$ Modulo $4$, this is the same as twice the number of blocks that straddle the planes $x=a$ or $y=b$ (the blocks the centers of which the line $(x,y)=(a,b)$ passes through should be counted only once here, not twice). We see that one of these lines must pass through the centers of at least $4$ blocks. If not, then this total number of blocks is exactly $2$ for each of these lines; however, there are $8n-5\equiv 1\bmod 2$ such lines.

So, we have a set of lines $L$ such that, for each pair of intersecting planes inside our $2n\times2n\times2n$ cube, at least one of them contains a line in $L$. We need to lower-bound the size of this set $L$.

Lemma. Consider lines entirely inside a $u\times v\times w$ rectangular prism with $u+v+w$ even (so, if $u=v=w=2$, there are $3$ such lines). A set $L$ of these lines satisfies that, for any two intersecting (lattice) planes inside this rectangular prism, $L$ contains at least one line lying entirely on one of these planes. Then $|L|\geq \frac{u+v+w}2-1$.

Proof. We prove this by induction on $u+v+w$ with $u,v,w\geq 2$. Our inductive step will only deal with $u,v,w>2$, so we need to prove the case in which, without loss of generality, $u=2$ in our base case. We will do this after the inductive step.

Without loss of generality, let the line $(x,y)=(u-1,v-1)$ be in $L$. Consider a new construction $L'$ on a $u-1\times v-1\times w$ prism consisting of at most $|L|-1$ lines so that

• given a line $\ell\in L$ that is not on either $x=u-1$ or $y=v-1$, $\ell$ is added to $L'$,

• given a line $\ell\in L$ with $x=u-1$, the line $\ell-(1,0,0)$ is added to $L'$, and

• given a line $\ell\in L$ with $y=v-1$, the line $\ell-(0,1,0)$ is added to $L'$.

We see that $L'$ satisfies the required conditions, since a plane $P$ in the $u-1\times v-1\times w$ case contains a line in $L$ if and only if it contains a line in $L'$. This reduces $u+v+w$ by $2$ and the number of lines by (at least) $1$, so we may apply our inductive hypothesis to finish.

This argument works to reduce $u+v+w$ as long as there is a line that can be chosen that does not reduce any side length to lower than $2$, so if we cannot make the above argument we may assume that $u=2$ and that there are no lines of the form $(y,z)=(b,c)$ in $L$. Here, we must have that, for any $y=b$, the line $(x,y)=(1,b)$ is in $L$, and for any $z=c$ the line $(x,z)=(1,c)$ is in $L$, so $L$ is of size at least $$v+w-2=(v-2)+(w-2)+2\geq \frac{v+w}{2}=\frac{u+v+w}{2}-1,$$ finishing our proof. $\square$

So, $L$ is of size at least $3n-1$. This means that the number of blocks whose centers are intersected by some lines is at least $$2\left(3(2n-1)^2\right)+2(3n-1).$$ At $n=11$ this is $2710$, which is more than $2\cdot 11^3$, finishing the proof for a cube of side length $22$. Sadly, this is not strong enough to solve the $n=24$ case.

I encountered a two-dimensional counterpart of this problem when I was a schoolboy, reading a Russian translation from 1971 of Martin Gardner’s “Mathematical puzzles and diversions”. I add below the relevant parts of his article “Polyominoes and Fault-Free Rectangles” from “New mathematical diversions”.