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

Question

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$.

Answer 1

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.

Answer 2

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”.

Answer 3

I've written a program which implements a random construction similar to the one from my other answer, and used this program to find a tiling which blocks all lines for the case $n = 102$.

Unfortunately this isn't very insightful -- the tiling is random and (essentially) unstructured, and doesn't give much information about the nature of the problem. I would be interested to see a construction which could be reasonably verified by a human; my post is mainly intended to gain a little closure and to nail down a reasonable upper bound.

Approach (similar to other answer):

Again, for convenience we want to think of the $n \times n \times n$ cube as a $k \times k \times k$ cube of $2 \times 2 \times 2$ subcubes (which I'll just refer to as "cubes"), with centers at points in $\{1, 3, 5, \dots, 2k-1\}^3$. The main benefit of this idea is that it allows for very modular construction, where we can place a given configuration of tiles locally (filling completely a small number of adjacent cubes) without worrying about how this will affect the global structure of the tiling.

The idea is to place, for each line, a small configuration of tiles which blocks the line. The configuration used depends on the parity of the coordinates of the line. Consider a line in the $z$-direction, given by the equations $x = a$ and $y = b$. For any such line, our configuration will be placed at some level $h$, for an odd $h$ between $1$ and $2k-1$. If $a$ and $b$ are both odd, we place the first configuration below in the cube with center $(a, b, h)$. If $a$ is odd and $b$ is even, we place the second configuration below in the adjacent cubes with centers $(a, b-1, h)$, $(a, b+1, h)$. Similarly, if $a$ is even and $b$ is odd, we place the second configuration in the adjacent cubes with centers $(a-1, b, h)$, $(a+1, b, h)$. Finally, if $a$ and $b$ are both even, we place the third configuration below in the adjacent cubes with centers $(a-1, b-1, h)$, $(a-1, b+1, h)$, $(a+1, b-1, h)$, $(a+1, b+1, h)$.

Hopefully the diagrams make clear that if placed as described, a configuration will block its associated line. Rotated versions of the above configurations can be placed analogously in order to block lines in the $x$- and $y$-directions. Once we've chosen a level for each line, our work is done so long as the tile configurations, when placed at the associated levels, don't overlap: after placing these configurations, no cubes are only partially filled, so we can fill all the empty cubes according to the first configuration above, yielding a full tiling of the $n \times n \times n$ cube. Thus to build a good tiling, it's enough to give a list of levels for all lines which produces no overlap.

Results:

I wrote a program which implements the above idea by choosing levels at random for each line, one at a time. As it does this, the program builds a skeleton of the tiling, filling the cubes occupied by the specified configurations, checking that no overlap is produced. For a given line, if the chosen level produces overlap with previously placed blocking configurations, the program tries again, repeatedly choosing a new level at random until one that does not produce overlap is found. If it cannot find one, the program gives up.

In the case $n = 110$, the program is successful, empirically, about 80% of the time. For $n$ a little below this, it starts to fail most of the time. The smallest successful tiling I found was at $n = 102$. I've posted this in a pastebin file here. The tiling is formatted as three nested arrays in python syntax, such that the level for the line in the $x$-direction given by $y = a$, $z = b$ is xlist[a-1][b-1], the level for the line in the $y$-direction given by $x = a$, $z = b$ is ylist[a-1][b-1], and the level for the line in the $z$-direction given by $x = a, y = b$ is zlist[a-1][b-1]. I've also added python code which performs the verification step, of checking that no overlap is produced by placing configurations at the specified levels, in another pastebin file.

Answer 4

Below is a probabilistic proof that such tilings exist for all sufficiently large (even) $n$. I recognize this might not be in the spirit of the question, since the method is non-constructive, but I thought it would be good to rule out impossibility proofs.

Building the (random) tiling:

For $n = 2k$, think of the $n \times n \times n$ cube as a $k \times k \times k$ cube of $2 \times 2 \times 2$ subcubes (I'll refer to these as just "cubes" going forward), with centers at points in $C = \{1, 3, 5, \dots, 2n-1\}^3$.

Independently assign to each of these cubes a tuple at random from the set $$D = \{x, y, z\} \times \{-1, 0, 1\} \times \{-1, 0, 1\}$$ according to some fixed distribution $p$ over $D$ to be chosen later. Loosely speaking, this tuple indicates the line that the cube is "assigned" to block: for example, if a cube centered at $(a, b, c)$ is assigned $(z, i, j)$, then the cube will attempt to block the line in the $z$-direction given by $x = a+i$, $y=b+j$ (similarly, if assigned $(x, i, j)$, the line $y = b + i$, $z = c + j$, and if $(y, i, j)$, the line $z = c+i$, $x = a+j$). The meaning of this will become clear once we construct the tiling. Let $F$ denote the resulting random assignment $C \to D$.

Now, given the assignment $F$, we construct the tiling as follows. Consider a cube centered at $(a, b, c)$, and suppose WLOG that it is assigned to block a line in the $z$-direction.

Case 1: If $F(a, b, c) = (z, 0, 0)$, the cube is assigned to block the line $x = a, y = b$, so we simply place two $2 \times 2 \times 1$ blocks in the cube, arranged as below to block the line.

Case 2: If $F(a, b, c) = (z, 1, 0)$, the cube is assigned to block the line $x = a+1, y = b$. This line meets the cube along one of its faces, and so the cube can only block the line if the cube on the other side of this face "cooperates", i.e. if the cube centered at $(a+2, b, c)$ is assigned the same line, meaning $F(a+2, b, c) = (z, -1, 0)$. In this case, we place four $2 \times 2 \times 1$ tiles in the two cubes in order to block the line as shown below:

We can place the tiles analogously in the case $F(a, b, c) = (z, 0, 1)$, if $F(a, b+2, c) = (z, 0, -1)$ as well.

Case 3: If $F(a, b, c) = (z, 1, 1)$, the cube is assigned to block the line $x = a+1, y = b+1$. This line meets the cube along one of its edges, and so the cube can only block the line if the three other cubes meeting at that edge all cooperate, i.e. that they are all assigned to the same line. This means $F(a+2, b, c) = (z, -1, 1)$, $F(a+2, b+2, c) = (z, -1, -1)$, and $F(a, b+2, c) = (z, 1, -1)$. In this case, we place eight tiles in the four cubes to block the line as shown below:

We place tiles in cubes assigned lines in the $x$- or $y$-directions according to the analogous conditions to cases 1, 2, 3. After tiles are placed for all cubes satisfying these conditions, we are only left with empty and full cubes, i.e. no cubes are only partially filled by tiles. Thus for the remaining cubes we can separately fill them with tiles according to the diagram in case 1; no conflicts are created. At the end, we have a complete tiling of the $n \times n \times n$ cube.

Analysis:

We can now analyze the probabilistic properties of the resulting tiling. For convenience, let's say the distribution $p$ over $D$ satisfies \begin{align*} p(w, 0, 0) &= q_1 \\ p(w, \pm 1, 0) = p(w, 0, \pm 1) &= q_2 \\ p(w, \pm 1, \pm 1) &= q_3 \\ \end{align*} where $w = x, y, z$, for some $q_1, q_2, q_3 > 0$.

Consider the probability that a line in the $z$-direction, say the line $L$ given by $x = a, y = b$ (for some $1 \leq a, b \leq 2n-1$), is not blocked.

Case 1: $a$ and $b$ are both odd. This can only happen if none of the cubes with centers along the line are assigned to block it. Each such cube is assigned to block it with probability $q_1$, and there are $k$ cubes which are assigned lines independently, so the probability that $L$ is not blocked is at most $(1 - q_1)^k$.

Case 2: One of $a$ or $b$ is odd, the other even. Say $a$ is odd. Note that for each odd $c$, $L$ is blocked if both the cubes at $(a-1, b, c)$ and $(a+1, b, c)$ are assigned to it, and this happens with probability $q_2^2$. Since there are $k$ such pairs of cubes, assigned independently, the probability that $L$ is not blocked is at most $(1-q_2^2)^k$. The same holds if $a$ is even and $b$ is odd.

Case 3: $a$ and $b$ are both even. This time, for each odd $c$, $L$ is blocked if all four cubes at $(a \pm 1, b \pm 1, c)$ are assigned to it, and this happens with probability $q_3^4$. Since there are $k$ such groups of four cubes, the probability that $L$ is not blocked is at most $(1 - q_3^4)^k$.

There are $k^2$ lines matching the first case, $2k(k-1) \leq 2k^2$ matching the second case, and $(k-1)^2 \leq k^2$ matching the third case. The same holds for the analogous cases in the $x$- and $y$-directions, so the probability that there is some line which is not blocked is at most $$3k^2((1 - q_1)^k + 2(1 - q_2^2)^k + (1 - q_3^4)^k).$$ For any choice of $q_1, q_2, q_3$, this goes to $0$ as $k \to \infty$, so in particular the probability that all lines are blocked is positive for sufficiently large $k$, meaning that tilings which block all lines exist for sufficiently large $k$.

Upper bound:

To get a tangible upper bound on the smallest $n$ for which such such tilings exist, we can try to choose $q_1, q_2, q_3$ to minimize the above expression. The expression is dominated by the term corresponding to the smallest of $q_1, q_2^2, q_3^4$, so we will set $q_1 = q_2^2 = q_3^4$, so there is some $r > 0$ with $q_1 = r^4$, $q_2 = r^2$, $q_3 = r$. For $p$ to be a distribution, we must have $1 = 3q_1 + 12q_2 + 12q_3$, so we can take $r = 0.077343...$ to be the unique positive root of $3r^4 + 12r^2 + 12r = 1$. Then under this choice of $p$, the probability that some line is not blocked by our tiling is at most $12k^2(1-r^4)^k \leq 12k^2 e^{-r^4 k}$, which is decreasing for $k$ greater than $2r^{-4} \leq 56000$, and dips below $1$ by $k = 850000$. Thus tilings blocking all lines exist for even $n \geq 1700000$.

This is a fairly rough upper bound, and can be improved slightly by a less wasteful construction/analysis. There are also other probabilistic constructions which seem to give better bounds, but I don't see an obvious way to get near the appropriate order of magnitude (say, $n \leq 1000$).

Answer 5

I expect that a required construction exists for sufficiently large $n$ and it should be shown by a concrete example. But I think that a corresponding tiling is rather irregular, so hard to describe and its construction is a quest rather for a puzzle solver than for a mathematician. So I crossposted it at Puzzling.SE.

Since the considered tilings are too complicated to be dealt by hand, I wrote an assisting program. I share it to facilitate other MSE users to solve the problem, and, possibly, to win the bounty. The program has a simple and intuitive interface, which looks a bit like “Tetris”, see a program screenshot. An the main working field are shown two consecutive layers of the cube of a selected size, parallel to one of three coordinate planes, which can be selected too. The bricks can be added or removed in a few clicks, see the program help for details. To facilitate diversity, each new brick obtains a personal random color. The red dots indicate the unblocked lines, perpendicular to the respective coordinate planes. Constructed partial tilings can be saved and loaded. Downloads: an executable file for Windows, a zip-archive of Delphi 5 source files. I devoted to a program a separate answer for possible related questions or discussions, for instance, reported bugs or proposed improvements. Also I described the problem to my colleague, Dr. Misha Mytrofanov, who got interested in it and is going to work with the program today.