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).
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$.
from Hot Weekly Questions - Mathematics Stack Exchange
Jyrki Lahtonen
Post a Comment