I saw the following problem in Mathematical Puzzles from Peter Winkler (very good book, by the way): imagine you infect k cases of a chessboard nxn and the infection spreads to a case if it has at least two neighbors infected. Then k = n is the minimum number such that it is possible to infect the whole chessboard. I would like to know if it is known what happen in higher dimensions and other values for the number of neighbors for a case to be infected?
$\begingroup$
$\endgroup$
4
-
3$\begingroup$ The magic words are bootstrap percolation. $\endgroup$– Anthony QuasCommented Nov 14, 2014 at 18:13
-
1$\begingroup$ bootstrap percolation consider a initial probability for each case to be infected, isn't it? Here is the goal is not to find the threshold but the exact number. $\endgroup$– Quentin FortierCommented Nov 14, 2014 at 19:05
-
1$\begingroup$ @AnthonyQuas so that is what "squeamish ossifrage" actually meant? $\endgroup$– Noam D. ElkiesCommented Nov 20, 2014 at 4:33
-
1$\begingroup$ @NoamD.Elkies: Good comment for the well-informed (or those with access to google like me) $\endgroup$– Anthony QuasCommented Nov 20, 2014 at 5:21
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
0
There is an d-dimensional version of this problem in The Art of Mathematics - Coffee Time in Memphis by Bela Bollobas. (Problem 35)
According to it, the answer is $k = \lceil d(n-1)/2 \rceil + 1$.
