A 2015-sided cube has some of its cells (unit cubes) been affected by an unknown infection. The infection spreads in such a way that if at least $t$ cells in a row parallel to one of the cube's edges are infected $(1 \leq t \leq 2015)$, then one minute later all cells in that row will become infected. Determine how many initially infected cells are required for

a) it to become possible,

b) we can be certain,

that the infection will reach all cells of the cube.
Solution. a) For the infection to spread completely, at least $t^{3}$ infected fields are initially required. In such a case, it is indeed possible for the infection to spread, for example, if the infected fields are initially located in a $t \times t \times t$ sub-cube. In this case, it is easy to see that all fields will be infected within 3 minutes: after 1 minute, the rows defined by the $t \times t \times t$ cube's rows, after 2 minutes, the planes defined by the $t \times t \times t$ cube's planes, and finally, after 3 minutes, the remaining fields.

Proving that fewer than this number of infected fields cannot result in complete spread requires a proof that goes beyond high school curriculum; see, for example, the article attached to the online solution of the problem 1.

Now let's address part b) of the problem.

$2015^{3}-(2015-(t-1))^{3}$ infected fields are not necessarily sufficient. If these infected fields are placed such that a $(2015-(t-1))$-edged cube remains in one corner, then in every row (where "row" refers to a row parallel to one of the cube's edges), there will be only $t-1$ infected fields, so the infection will not spread further.

However, if there are already $2015^{3}-(2015-(t-1))^{3}+1$ infected fields, it can be shown that the entire cube will definitely become infected.

Let's examine how many infected fields are required for a 2-dimensional $2015 \times 2015$ "layer" of the cube to definitely become infected. If there are at least $t$ rows in the $x$ direction with at least $t$ infected fields, then the entire layer will definitely become infected. If this condition is not met, it means that there are at least $2015-(t-1)$ rows in the $x$ direction with at most $t-1$ infected fields. The remaining $t-1$ rows can have at most 2015 infected fields, so in total, there are at most

$$
(2015-(t-1))(t-1)+2015(t-1)=2015^{2}-(2015-(t-1))^{2}
$$

If there are fewer than $(t-1)$ rows with fewer infected fields, this naturally allows for even fewer infected fields in total. Therefore, if a layer has more than $2015^{2}-(2015-(t-1))^{2}$ infected fields, it must have at least $t$ rows with at least $t$ infected fields, and these rows will become completely infected in the next minute. This ensures that every row in the $y$ direction will have at least $t$ infected fields, and thus everything will become infected.

Similarly, if there are at least $t$ layers in the $x-y$ direction with at least $2015^{2}-(2015-(t-1))^{2}+1$ infected fields, the entire cube will definitely become infected, since, as we have shown, every layer will become completely infected, and then every row in the $z$ direction will have at least $t$ infected fields, ensuring that everything becomes infected. If this condition is not met, it means that there are at least $2015-(t-1)$ layers with at most $2015^{2}-(2015-(t-1))^{2}$ infected fields, and the remaining $t-1$ layers can have at most $2015^{2}$ infected fields, so in total, there are at most

$$
\begin{gathered}
(2015-(t-1))\left(2015^{2}-(2015-(t-1))^{2}\right)+2015^{2}(t-1)= \\
=2015^{3}-(2015-(t-1))^{3}
\end{gathered}
$$

infected fields, in which case it is not certain that every field will become infected. Therefore, with $2015^{3}-(2015-(t-1))^{3}+1$ infected fields, the entire cube will definitely become infected.

Note. For part a), a maximum of 1 point was awarded. Part b) was worth 3 points, so a total of 4 points could be earned for the problem. The Mathematics Committee apologizes to the contestants for any inconvenience. [^0]

[^0]:    ${ }^{1}$ Paul N. Balister, Béla Bollobás, Jonathan D. Lee, and Bhargav P. Narayanan: Line percolation;