Medium | Discrete Maths |

An infection spreads among the squares of an nXn checkerboard in the following manner. If a square has two or more infected neighbors, it becomes infected itself. (Each square has 4 neighbors only!). Prove that you cannot infect the whole board if you begin with fewer than n infected squares.

Hint

Invariance

Solution

Perimeter of infected area can't increase. It stays constant or decreases. Initially maximum perimeter is 4*k if k blocks are infected. But to infect all blocks, the perimeter must increase to 4*n, k<n. This is not possible

Source: P. Winkler

Enable Like and Comment Latest solved Puzzles

Color Switches Weird Sequences Intersecting Pillars Consecutive sums Scaling a Square Difficulty Level

© BRAINSTELLAR |