156. A cube with edge length $n$ is divided into $n^{3}$ unit cubes. We select several cubes and draw three lines through the center of each, parallel to the edges. How many cubes can be chosen at a minimum so that the lines drawn through them cross all the cubes?

a) Provide the answer for small values of $n$: for $n=2,3,4$.

b)* Try to find the answer for $n=10$.

c)* Solve the general problem. If you cannot find an exact answer, prove some inequalities that estimate the number of marked cubes from above and below.

d)* Notice that this problem can be formulated as follows.

Consider all possible sets ( $x_{1}, x_{2}, x_{3}$ ), where each of the letters $x_{1}, x_{2}, x_{3}$ takes one of $n$ values $1,2, \ldots, n$. What is the smallest number of sets that need to be chosen so that for each of the remaining sets, there is one among the chosen sets that differs from it in only one place (the value of only one of the coordinates $x_{1}, x_{2}, x_{3}$ )? Try to find the answer for a more general problem, where sets of not three, but four or more letters are considered.
156. Answer: the smallest number $A_{n}$ of cubes satisfying the condition is

$$
A_{n}= \begin{cases}n^{2} / 2, & \text { if } n \text { is even, } \\ \left(n^{2}+1\right) / 2, & \text { if } n \text { is odd. }\end{cases}
$$

In particular, $A_{2}=2, A_{3}=5, A_{4}=8, A_{5}=12, A_{10}=50$.

The proof that fewer cubes cannot suffice can be conducted as follows. For the arrangement of cubes satisfying the condition: in each cell of the bottom face of the cube, we write the number indicating how many cubes lie above this cell. We will now use the following lemma.

Lemma. In an $n \times n$ table, non-negative integers are arranged, and for each pair of row and column intersecting at zero, the sum of $2n-1$ numbers in their union (the "cross") is at least $n$; then the sum of all numbers in the table is at least $n^{2} / 2$.

Its proof is very similar to the reasoning in problem 126.

If the smallest of the sums of rows and columns—let this be the sum of the numbers in the first row—is $m<n$, then in this row there are at least $n-m$ zeros, and in each of the $n-m$ columns starting with these zeros, the sum of the numbers is at least $n-m$, and in each of the $m$ remaining columns, the sum of the numbers is at least $m$, so the total sum is at least

$$
(n-m)^{2}+m^{2} \geqslant n^{2} / 2
$$

An example of the required arrangement of 12 cubes in a $5 \times 5 \times 5$ cube and 50 cubes in a $10 \times 10 \times 10$ cube is shown in Fig. 64, where the number in the cell indicates the layer in which the cube should be placed above the given cell. Analogous constructions can be made for other $n$.

$\nabla$ The most interesting result for the $k$-dimensional case is the lower bound on the number of "cubes" ( $x_{1}, \ldots, x_{k}$ ), given that no two of them differ in only one coordinate: their number does not exceed $n^{k-1} / k-1$. The exact answer for $k \leqslant 1$ is apparently unknown in the general case [65].
![](https://cdn.mathpix.com/cropped/2024_05_21_7b8a6b2625543c3dae75g-167.jpg?height=454&width=740&top_left_y=258&top_left_x=228)

Fig. 64