3
$\begingroup$

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.

$\endgroup$
13
  • 2
    $\begingroup$ 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. $\endgroup$
    – Vepir
    Jan 9 at 19:27
  • $\begingroup$ 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. $\endgroup$
    – ologn13
    Jan 9 at 19:36
  • 3
    $\begingroup$ 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. $\endgroup$
    – Vepir
    Jan 9 at 19:54
  • $\begingroup$ 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 :) $\endgroup$
    – ologn13
    Jan 9 at 23:16
  • 1
    $\begingroup$ Also asked on math.SE (math.stackexchange.com/questions/3988288/…) and MO (mathoverflow.net/questions/381576/…) $\endgroup$ Jan 19 at 0:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.