# Infected Cylinder and Torus

A variant of the well known Infected Checkerboard problem. If we've a 𝑛x𝑛 square, then we fold it along top and bottom row to form a cylinder. A cell in this cylinder becomes infected if at least two of its neighbors (orthogonal only) are infected. Prove that, initially, if the number of infected cells is less than 𝑛, the whole cylinder can't be infected.

Additionally, instead of cylinder, let's form a torus by joining the sides of the square. Prove that 𝑛-1 initial infected cells are necessary to infect the whole torus.

The square variant can be solved by observing the perimeter of the infected cells.

• Doesn't the same argument still apply? Except now you don't need to cover a perimeter of a n x n square, but of a (n-1) x n rectangle in the case of a cylinder, then of a (n-1) x (n-1) square in the case of a torus. – Vepir Jan 9 at 19:27
• A cylinder would still have n x n cells (and same for torus) as we're not merging the top & bottom row but concatenating them with sides. – ologn13 Jan 9 at 19:36
• Yes, we still have n x n cells but we only need to infect (n-1) x n sub-rectangle or (n-1) x (n-1) sub-square (using the perimeter argument), because then the infection automatically spreads to the remaining cells (because of the folding) and infects the entire cylinder or torus. – Vepir Jan 9 at 19:54
• I think you’re right. I complicated things unnecessarily and was thinking why do we necessarily need to have n-1 x n rectangle infected first. But it’s obvious that the rectangle will inevitably be involved as part of infecting the whole cylinder. Thanks! Unfortunately I‘m unable to upvote your comment, so if you can add it as an answer I’ll be happy to accept it :) – ologn13 Jan 9 at 23:16
• Also asked on math.SE (math.stackexchange.com/questions/3988288/…) and MO (mathoverflow.net/questions/381576/…) – Ilmari Karonen Jan 19 at 0:44