riddle of the day

Ninety-nine infected squares on a board of ten thousand. If you place them cleverly, can the infection take over every last square?

The Board Infection

Master
Pure logic

Riddle statement

On a \(100\times100\) board, you may choose exactly 99 squares to be infected initially.

The infection then spreads in rounds: in each round, every healthy square sharing a side with at least two infected squares becomes infected. Infected squares never recover.

Can you choose the 99 starting squares so that, sooner or later, the entire board becomes infected?

Show solution

Solution

Answer: No. No choice of 99 initially infected squares can eventually infect the entire board.

The key is not to count infected squares, but to measure the boundary of the infected region.

Let \(P\) be the number of unit edges that either:

  • separate an infected square from a healthy square; or
  • separate an infected square from the outside of the board.

1. The boundary can never increase.

Suppose a healthy square becomes infected and currently has \(k\ge2\) infected side-neighbors.

Before the infection, the \(k\) edges shared with those neighbors belong to the boundary. Once the square becomes infected, those edges lie between two infected squares and disappear from the count.

The other \(4-k\) edges become part of the new boundary: they face healthy squares or, when the square lies on the edge of the board, the outside.

Therefore,

$ \Delta P=(4-k)-k=4-2k. $

Since \(k\ge2\),

$ \Delta P\le0. $

Every infection therefore preserves or decreases the boundary; it can never increase it.

If several squares become infected simultaneously during one round, we may inspect them one at a time in any order. Each already had at least two infected neighbors at the start of the round, and processing other infections first can only increase that number. The same inequality still applies.

2. The initial boundary is too small.

Each of the 99 initially infected squares can contribute at most four boundary edges. Hence

$ P_0\le4\cdot99=396. $

This upper bound holds regardless of where the 99 squares are placed.

3. A fully infected board would require a larger boundary.

If all 10,000 squares were infected, no internal edge would belong to the boundary. Only the outer edge of the board would remain.

Each of its four sides has length 100, so

$ P_f=4\cdot100=400. $

But \(P\) starts at no more than 396 and can never increase. It cannot finish at 400.

Therefore, 99 starting squares can never infect the entire board.

Key idea: the infection may occupy more and more squares, but it cannot create the amount of boundary required by the fully infected board.