9
$\begingroup$

(Now cross-posted to Puzzling SE.)

3D infected cubes puzzle with threshold $4$:
On an $n\times n\times n$ cube, some cells are infected; if a cell shares a face with $4$ infected cells, it becomes infected. What's the minimum number of initially infected cells required to infect the whole cube?

The two-dimensional, threshold $2$ version is a classic. The solution to that puzzle (often simply called the "infected squares puzzle") is $n$.

The two-dimensional, threshold $3$ version is more interesting. When $n$ is of the form $2^k-1$, the solution is $\frac{4^k-1}3=\frac13n^2+\frac23n$ with an interesting recursive pattern. When $n$ is not of that form, I believe that the solution is $\lceil\frac13n^2+\frac23n+\frac13\rceil$ for odd $n$ and $\lceil\frac13n^2+\frac23n+\frac43\rceil$ for even $n$. (I don't have a proof but I think someone else does.) In summary: $\frac13n^2+\frac23n+O(1)$.

Up a dimension, the three-dimensional, threshold $3$ version is simple again. The answer is $n^2$. In fact, the $d$-dimensional, threshold $d$ version is solved for all $d$: see here.

The logical next step, then, is the three-dimensional, threshold $4$ version. After some thinking, I have some conjectural upper bounds:

$n=1$ is $1$, trivially.
$n=2$ is $8$. (In fact, for all $n\ge2$, the $8$ vertices must start infected, as they only have three neighbors.)
$n=3$ should be $14$ (corner cells and face cells).
$n=4$ should be $33$.
$n=5$ should be $53$ (I previously wrote $52$ but I don't think that works actually).

What more progress can be made? Are the solutions I found for $n\le5$ minimal? Is there a formula (even an asymptotic one) for general $n$?

For what it's worth, I can manage a lower bound of $\frac14n^3+\frac34n^2$. However, given the data above, this doesn't seem to be an especially close bound.

A helpful observation: Consider the $(n+1)^3$ points that are vertices of a cell. I believe that this set ("the grid points") must be connected through the infected cells: that is, the set of these grid points union the set of infected cells must be a connected set. (This observation is true of the two-dimensional, threshold 3 version as well. However, in that case, it was both a necessary and sufficient condition; in our case, this is still necessary but no longer sufficient.)

$\endgroup$
4
  • 1
    $\begingroup$ If you do not get a response on MSE, I suggest posting on puzzling.stackexchange.com as well (being sure to tell people you previously asked on MSE). $\endgroup$ Dec 2, 2022 at 15:51
  • $\begingroup$ Yikes. Neat problem, but I can't even figure a solution for $n_2(7)=21$, so I'm not sure how to work in three dimensions without just programming a solver. $\endgroup$ Dec 4, 2022 at 0:09
  • $\begingroup$ @EricSnyder You'll get there… as a hint, $n_2(3)=5$ (with your notation) and $21=4(5)+1$. $\endgroup$ Dec 4, 2022 at 0:14
  • $\begingroup$ Oh, wow, in retrospect that should have been obvious... $\endgroup$ Dec 4, 2022 at 0:26

1 Answer 1

2
$\begingroup$

For every other layer of the cube (including the bottom and top layer), initially infect every other cell (in a checkerboard pattern), plus the edges. This completely infects those layers, and gives the cells in the remaining layers two infected neighbors to start with, reducing the problem in those layers to the $d=2$, threshold $2$ problem. Then infecting a long diagonal of each remaining layer infects all the remaining cells. Since we filled half the layers halfway, and the remaining ones very sparsely, the total number of initially infected cells is $n^3/4 + O(n^2)$. (This is an upper bound; if OP has established it as a lower bound as well, then the exact answer is $n^3/4 + O(n^2)$.)

A related approach is to infect the bottom layer first, reducing the problem in the layer above it to the $d=2$, threshold $3$ problem. Then repeat this for each layer: infect as many as necessary to get the whole layer infected (known/believed to be $n^2/3 + O(n)$), giving all the members of the next layer one infected neighbor. Here the total number of initially infected cells is $n^3/3 + O(n^2)$. (This isn't quite as efficient in the large-$n$ limit, but it seems plausible that, for smaller $n$, the optimal solutions may look more like this... with layers uniformly infected to start with... than like the alternating-layer solution in the first paragraph.)

$\endgroup$
1
  • $\begingroup$ Wonderful! So the answer is $\frac14n^3+O(n^2)$, and now it's a matter of finding the lower-order terms. This long-term beats the answer given on Puzzling SE, which achieves $\frac{15}{56}n^3+O(n^2)$, though only for $n=2^k-1$. That said, short-term theirs wins: for $n=7$ your approach gives $165$, and theirs gives $130$. (My lower bound says it's at least $123$, though I would not be surprised if the true answer were much closer to $130$.) $\endgroup$ Dec 6, 2022 at 18:18

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .