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.

Improve this question
$\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, 2021 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$
    – user73244
    Jan 9, 2021 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, 2021 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$
    – user73244
    Jan 9, 2021 at 23:16
  • 1
    $\begingroup$ Also asked on math.SE (math.stackexchange.com/questions/3988288/…) and MO (mathoverflow.net/questions/381576/…) $\endgroup$
    – Ilmari Karonen
    Jan 19, 2021 at 0:44

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.