The Infected Checkerboard
An infection spreads among the squares of an n x n checkerboard in the following manner. If a square has two or more infected neighbors, then it becomes infected itself. (Neighbors are orthogonal only, so each square has at most four neighbors.) For example, suppose that we begin with all n squares on a main diagonal infected. Then the infection will spread to the whole board.
Prove that you cannot infect the whole board if you begin with fewer than n infected squares.
Prove that you cannot infect the whole board if you begin with fewer than n infected squares.
posted by Zaux at
7:42 AM
3 Comments:
infected checkerboard
1st consider a 1x1 board.
-obviously to fill it, we need 1 infected square
consider 2x2 board
-we must fill diagonal with 2 infected squares
-looking at the filled infected 2x2 square we note that if it was placed within a 3x3 board no more squares would be infected i.e. one more filled square at the diagonal is required for full infection
we can't improve on this since the 2x2 original square uses the minimum amount to fill itself
all subsequent boards can be place in a board one larger until the nxn sized board is reach, which uses:
2+(n-2) OR n infected squares
Cam
I should state that the "minimum number of infected squares to fill an nxn square" is x identified in the problem of "largest nxn square x infected squares can fill" if the size of the squares match
i.e. if 3 infected squares can fill up to a max of a 3x3 square then the minimum # of infect squares required to fill a 3x3 square is 3
Cam
To clarify even further,
if we have found that x infected squares may fill a maximum of nxn squares, it is trivial to say that any larger square (including a (n+1)x(n+1) square) must use at least 1 more infected square
Cam
Post a Comment
Links to this post:
Create a Link
<< Home