Jump to content
BrainDen.com - Brain Teasers
  • 0

Question

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 by bushindo
Link to post
Share on other sites

8 answers to this question

Recommended Posts

  • 0

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.

Link to post
Share on other sites
  • 0

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 by phillip1882
Link to post
Share on other sites
  • 0

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 by KlueMaster
Link to post
Share on other sites
  • 0

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...

Link to post
Share on other sites
  • 0

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 by plasmid
Link to post
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Answer this question...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

Loading...
  • Recently Browsing   0 members

    No registered users viewing this page.

×
×
  • Create New...