[bushindo]

Let's say we have 343 biological cells stacked into a 7x7x7 cube. In this arrangement, each cell is surrounded by a maximum of 6 neighbors. The cells can be infected with a disease. In particular, if a healthy cell is surrounded by 3 or more infected cells, it will become infected as well.

What is the minimum number of infected cells that you need in the beginning that is guaranteed to eventually infect the entire 7x7x7 cube?

Edited December 23, 2010 by bushindo

[k-man]

Without putting too much thought into it, my first guess is that if 3 adjacent sides of the cube are completely infected then the infection will spread throughout the cube, so we need to infect 3 adjacent sides. This can be done by seeding the infection in the checker-like pattern throughout these sides with the corners infected. So, using this method the initial number of infected cells required is 64.

It probably can be done with fewer infected cells, but this is all I got for now.

[k-man]

I can reduce the initial number to 61 by not infecting the 3 cells in the centers of the sides. They will get infected anyway.

EDIT: misspelling

Edited December 23, 2010 by k-man

[Guest]

obviously the sides and corners will be the hardest to infect since they have the fewest nieghbors.

i would agree with k-mans assessment, infecting three sides should give you the victory, however, i believe there is a more optimal arrangement.

        _ _ _ _ _ _ _

      /I/I/I/_/I/_/I/|

     /I/_/_/I/_/_/I/ |

    /I/_/I/_/_/I/_/  |

   /_/I/_/_/I/_/_/   |

  /I/_/_/I/_/_/I/    |

 /I/_/I/_/_/I/_/     |

/_/I/_/_/I/_/_/      |

|_|I|_|_|I|_|_|      /

|I|_|_|I|_|_|I|     /

|I|_|I|_|_|I|_|    /

|_|I|_|_|I|_|_|   /

|I|_|_|I|_|_|I|  /

|I|_|I|_|_|I|_| /

|I|I|_|I|I|_|I|/

this gives 56 infected cells.

Edited December 23, 2010 by phillip1882

[Guest]

Let's say we have 343 biological cells stacked into a 7x7x7 cube. In this arrangement, each cell is surrounded by a maximum of 6 neighbors. The cells can be infected with a disease. In particular, if a healthy cell is surrounded by 3 or more infected cells, it will become infected as well.

What is the minimum number of infected cells that you need in the beginning that is guaranteed to eventually infect the entire 7x7x7 cube?

I tried visualizing the problem as a 2-D arrangement and then expanding the same into 3D.

if you infect all the cells across all major diagonals, rest all cells will be infected eventually...

so you need to infect only 25 cells...

Though, I still feel there may be a way to do the trick by infecting 3 diagonals only.

Edited December 24, 2010 by KlueMaster

[Guest]

I tried visualizing the problem as a 2-D arrangement and then expanding the same into 3D.

if you infect all the cells across all major diagonals, rest all cells will be infected eventually...

so you need to infect only 25 cells...

Though, I still feel there may be a way to do the trick by infecting 3 diagonals only.

err, I ignored the fact that you are only counting only 6 neighbors...

both linear as well as oblique diagonals, i.e. 16*3 + 1 = 49 cells to be corrupted...

[plasmid]

Point of clarification: are you asking for the smallest number of cells that can generate a pattern that will eventually spread to infect the entire cube, or are you asking for the smallest number of cells that will (regardless of their initial distribution) be guaranteed to eventually infect the entire cube?

The second case seems fairly easy.

Consider a cube with everything except one edge of 7 cells infected. That edge will never become infected. So that's a case of having 7x7x7-7 = 336 infected cells that will not guarantee complete infection, and the minimum number needed to guarantee infection would be 337.

For the first case, I can do it in 52.

I can get an entire 7x7 face infected with 21 cells using this pattern. It should be fairly clear how this will eventually infect the entire face.

X X X X

 X   X

X X X X

   X

X X X X

 X   X

X X X X

As the others have pointed out, infect three faces of the cube and the infection will eventually infect the entire cube (I could go through the details of how that would work if you're having trouble visualizing it). I'll just expand that a bit to say that three faces (including their involved edges and corners) would be three faces (excluding the edges and corners) plus seven of the eight corners plus nine of the twelve edges. Graphically...

+-----+

|     |\

|     | \

|     |  +

+-----+  |

 \     \ |

  \     \|

   +-----+

With the pattern above, I'm starting with each of the corner cells infected, so for the cube the 7 corners that contact at least one of the three involved faces will start out infected. For each edge (excluding the corners) there are two infected cells, so for the 9 edges involved for the cube, there will be be (2x9) infected cells. Finally for the faces, there are 9 infected cells per face that are not on an edge or a corner, so for the 3 involved faces of the cube there will be (9x3) cells used. Total number of cells I would need for the cube is (corners) + (edges) + (faces) = (7) + (2x9) + (9x3) = 52.

But I can't prove that this is optimal. Maybe KlueMaster could flesh out the proposed solution with 49, I don't think that infecting the diagonals alone would actually do it, but maybe I'm missing something.

Edited December 24, 2010 by plasmid

[bushindo]

I'm intrigued with KlueMaster's solution with 49 cells as well. If KlueMaster could elaborate on it, that would be great.

[Guest]

i'm guessing cluemaster mean this:

extended to all 6 quadrants.

which doesn't really work.