19
$\begingroup$

There is a dangerous bacteria, Checkerichia Coli, (or C. Coli for short) which lives in the squares of checkerboards. Squares with this bacteria living in their digestive systems are said to have "C-sickness". Once a square has "C-sickness," it is stuck with it forever!

Excessive contact with C-sick squares will cause a square to become C-sick. Specifically, if a healthy square has at least two C-sick neighbors (orthognal, not diagonal), then that square becomes C-sick the next day.

For example, on the left we the photo of a see a partially infected checkerboard which was taken yesterday. On the right is a photo taken today.

enter image description here

  • Warmup: A bioterrorist has 8 samples of the C. Coli strain, each of which can infect a single square. Which squares of an 8 by 8 chessboard can he infect so the infection will spread to the entire board?
  • Challenge: If the terrorist has only 7 samples, can he still infect the whole board?

I didn't invent this puzzle, it is quite famous, but the puns are my own.

$\endgroup$
18
$\begingroup$

This is a pretty common puzzle.

Warm up Answer:

The 8 cells along the diagonal.

Advanced Answer Explanation:

No, it is impossible. However, we are instead looking at the number of edges rather than pieces. In an $n$ x $n$ checkerboard, the perimeter is $4n$, which means that the number of edges our infection must have when fully covering the board is $4n$. When initially starting with $n-1$ infections, the maximal perimeter of these infections is $4(n-1)$. Now, I am going to show that new infections at best, maintain the perimeter rather than enlarging it.

If the infections enclose an open cell (bordering all 4 sides), it clearly turns into further infection. However this case causes the overall perimeter of the infection to decrease by 4 because it loses 4 edges and gains 0 new ones.

If an infection borders a cell on 3 edges (which is rotationally equivalent), then it will infect the cell causing it lose these 3 edges and gain only 1 new edge, for a loss of 2 edges.

Finally is the case where a cell is bordered on 2 edges by other infected cells. This can either be top/bottom (which is rotationally equivalent to left/right), or the 2 infected cells are touching diagonally and so the healthy cell is bordered by both sides along a corner. However in either case, this healthy cell gets infected and creates 2 new edges, while losing 2 edges in the process remaining edge neutral. Thus this shows that edges can never be created, and it is therefore impossible to have less than $n$ initial infections.

$\endgroup$
4
$\begingroup$

This isn't really an answer, but more of a hyper-extended comment. I have made a program that simulates the infection of a board in JavaScript, to check on any particular setups.

TL;DR

Right-click on any HTML page and select “Inspect Element” (It's the bottom option in Firefox and Chrome. I don't know where it is otherwise, probably the same place.) Navigate to your browsers console. Copy the minified code and paste it into the command line into the console. (On Firefox, you will need to type “Allow Pasting” before being able to paste it.)

To create a new board, simply choose a name for your board (let's say you choose bob) and type var bob = new Board();.
To insert an infected cell, type at position $(x,y)$ bob.infect(x,y);. NOTE: The counting is zero-based. I have furnished a table in the commented code within the Board class that tells you which cell is which.
To see what the board looks like, type either bob.print() or console.log(bob.print());. The former only displays if it is the last line you have typed, so I'd suggest the latter.
To advance to the next day/stage of infection, type bob.nextDay().
To see what the value at position $(x,y)$ is, type console.log(bob.board[y][x]);.
To see what day/stage of the infection, type bob.day. There is a zeroeth day, and this means that this is the day before anything has happened; the insertion of infected cells. You can still insert cells on any other day, however.

Code

Commented Code

function Board(){
    this.width = this.height = 8;   // an 8x8 chess board
    var x = new Array();            // creating the 2d array
    for(var Zi=0;Zi<this.height;Zi++){
        x[Zi] = new Array();        // creating the y-axis of the 2d array
        for(var Zj=0;Zj<this.width;Zj++){
            x[Zi][Zj] = 0;          // populating the y-axis with 0
        }
    }
    this.board = x;                 // setting board to the 2d array
    this.day   = 0;                 // starting the board out on the first day
/*
     0 1 2 3 4 5 6 7 } i
    +---------------
  0 |0 0 0 0 0 0 0 0
  1 |0 0 0 0 0 0 0 0 
  2 |0 0 0 0 0 0 0 0 
  3 |0 0 0 0 0 0 0 0 
  4 |0 0 0 0 0 0 0 0 
  5 |0 0 0 0 0 0 0 0 
  6 |0 0 0 0 0 0 0 0 
  7 |0 0 0 0 0 0 0 0 
  v
  j
*/
}

Board.prototype.print = function(){
    var string = "\n";                              // for display purposes
    for(var i=0;i<this.height;i++){
        for(var j=0;j<this.width;j++){
            if(this.board[i][j])                    // displaying if occupied
                string += this.board[i][j] + " ";   // displaying the (j,i)th entry
            else
                string += "  ";
        }
        string += "\n";                             // spacing for the next array
    }
    return string;
}

Board.prototype.infect = function(x,y){
    // origin = top-left, (0,0)
    this.board[y][x] = 2;   // setting the (x,y)th entry to be “newly infected”
}

Board.prototype.nextDay = function(){   // advances the day, spreads infection
    // getting rid of any 2's from the last day.
    for(var y=0;y<this.height;y++){
        for(var x=0;x<this.width;x++){
            // !x return 0 if x != 0 and 1 if x == 0, so 
            // !!x returns 1 if x !=0 and 0 if x == 0
            // ~~x simply converts x to a number
            this.board[y][x] = ~~!!this.board[y][x];
        }
    }

    // creating the board to be the next day's
    var nextDayBoard = Array.from(this.board);
    for(var y=0;y<this.height;y++){
        for(var x=0;x<this.width;x++){
            // no need to act on the cell if its already infected
            if(!this.board[y][x]){
                // establishing “null” value if not present
                var topCell = 0;    
                // checking if there is a cell orthogonally above
                if(y>0){    
                    // get the top cell's coordinate 
                    var topCell = this.board[y-1][x];
                }

                // establishing “null” value
                var leftCell = 0;
                // checking if there is a cell orthogonally left
                if(x>0){
                    // get the left cell's coordinates
                    var leftCell = this.board[y][x-1];
                }

                // establishing “null” value
                var rightCell = 0;
                // checking for cell orthogonally right
                if(x<this.width-1){ // minus 1 due to zero-based indexing
                    var rightCell = this.board[y][x+1];
                }

                // establishing “null” value
                var bottomCell = 0;
                // checking for cell orthogonally below
                if(y<this.height-1){    // minus 1 due to zero-based indexing
                    var bottomCell = this.board[y+1][x];
                }

                // creating array of adjacent cells
                var adjacentCells = [topCell,leftCell,rightCell,bottomCell];

                /* 
                    Now, the current cell is infected iff 
                    there are two orthogonally adjacent 
                    cells. Therefore, taking the sum of
                    adjacentCells will give us how many
                    cells are infected that are adjacent
                    to the current cell.
                */

                // taking the sum of adjacentCells
                var infected = adjacentCells.reduce(function(previousCell,currentCell){
                    if(currentCell != 2) return previousCell + currentCell;
                    return previousCell;
                },0);

                // if the cell has become infected:
                if(infected>=2){
                    // setting the current sell to newly infected state,
                    // so there is now no way for it to effect other
                    // cells
                    nextDayBoard[y][x] = 2;
                }
                // we do not need to change the value otherwise,
                // so an else statement is not required
            }
        }
    }
    // incrementing the day.
    this.day++;
    // setting the board to the next-day board.
    this.board = nextDayBoard;
}

// different variables in for loops to makes sure
// no variable conflicts happen

// ----

// creating test board
var board = new Board();
board.infect(1,1);
board.infect(3,1);
console.log(board.print());
board.nextDay();
console.log(board.print());

// success!

// creating example board
var example = new Board();
// group 1
example.infect(1,1);
example.infect(2,1);
// group 2
example.infect(0,4);
example.infect(0,5);
example.infect(0,6);
example.infect(1,5);
// group 3 (last)
example.infect(3,4);
example.infect(4,3);
example.infect(5,4);
example.infect(5,6);
example.infect(6,5);
example.infect(6,7);
example.infect(7,6);
console.log(example.print());
example.nextDay();
console.log(example.print());
example.nextDay();
console.log(example.print());

Minified Code

function Board(){this.width=this.height=8;var x=new Array();for(var Zi=0;Zi<this.height;Zi++){x[Zi]=new Array();for(var Zj=0;Zj<this.width;Zj++){x[Zi][Zj]=0;}} this.board=x;this.day=0;} Board.prototype.print=function(){var string="n";for(var i=0;i<this.height;i++){for(var j=0;j<this.width;j++){if(this.board[i][j]) string+=this.board[i][j]+" ";else string+=" ";} string+="n";} return string;} Board.prototype.infect=function(x,y){this.board[y][x]=2;} Board.prototype.nextDay=function(){for(var y=0;y<this.height;y++){for(var x=0;x<this.width;x++){this.board[y][x]=~~!!this.board[y][x];}} var nextDayBoard=Array.from(this.board);for(var y=0;y<this.height;y++){for(var x=0;x<this.width;x++){if(!this.board[y][x]){var topCell=0;if(y>0){var topCell=this.board[y-1][x];} var leftCell=0;if(x>0){var leftCell=this.board[y][x-1];} var rightCell=0;if(x<this.width-1){var rightCell=this.board[y][x+1];} var bottomCell=0;if(y<this.height-1){var bottomCell=this.board[y+1][x];} var adjacentCells=[topCell,leftCell,rightCell,bottomCell];var infected=adjacentCells.reduce(function(previousCell,currentCell){if(currentCell!=2)return previousCell+currentCell;return previousCell;},0);if(infected>=2){nextDayBoard[y][x]=2;}}}} this.day++;this.board=nextDayBoard;}
$\endgroup$
3
$\begingroup$

For the first case:

Simply choose either diagonal to place the samples. This will cover the board in 7 days.

For the second case:

No unless he can move the samples after placing them. The samples end up growing to create a rectangle from the outermost points for each connected blob so it would be impossible with 7 otherwise.

$\endgroup$
  • $\begingroup$ But this assumes that the blob needs inner points thus the proof isn't sound. Consider the case, A1, B2, B4, D2, E7, G5, G7, and H8. There is a 4x4 area in the dead center that starts healthy, yet the whole map will become infected. $\endgroup$ – qwertylpc Jul 17 '15 at 15:53
2
$\begingroup$

Warmup:

He can just place his 8 samples diagonally (from a corner to the diametrically opposite one).

Challenge:

No. Every new sample (starting from inside to out) increases the width or height of the smallest rectangle/square that includes all the squares infected or can be infected with the samples by 2, or both its width and height by 1, and sometimes it doesn't have any effect. So if we had 7 samples, the rectangle/square would never reach 8x8.

Edit for those who might downvote it:

Even if the "nearest" new sample is more than 2 squares away from the old rectangle (2 squares for a single dimension or 1 for each dimension), we can group together all the "connected" samples less than 3 squares away from each other. If there are $n$ such groups and there are respectively $k_x, 0<x<n$ samples in them, at best their rectangles could cover $2+(k_1-1)*2 + ... + 2+(k_n-1)*2 = 2[k_1+...+k_n]$ = 14 units in total (sum of both dimensions of each rectangle). There must be gaps between the rectangles though, so we might need to make a more conservative guess. If two rectangles are connected, at worst the new rectangle's sum of dimensions would equal the total sum of the dimensions for the two and a bigger rectangle would take both of their place. Eventually there'll be only two connected rectangles left so the total SoD will never reach 16.

Edit 2:

Note that a 1x1 square can also be considered a rectangle with a SoD of 2. It's like an addition with full of parentheses that may be in weird places; you don't necessarily start "linearly", but eventually the sum will equal the "normal" sum found by adding everything up from left to right.

$\endgroup$
  • $\begingroup$ What the heck was wrong with my answer? $\endgroup$ – Nautilus Jul 17 '15 at 14:21
  • $\begingroup$ Is someone accusing me of stealing Quark's answer? $\endgroup$ – Nautilus Jul 17 '15 at 14:50
  • 2
    $\begingroup$ People (not myself) are downvoting because your proof is unsound. Not every row nor every column needs to have an infection for the board to be covered, thus an argument based on this is folly. An example with leaving rows 3 and 6 empty, as well as columns C and F is: A1, B2, B4, D2, E7, G5, G7, and H8. $\endgroup$ – qwertylpc Jul 17 '15 at 15:52
  • $\begingroup$ Edited. If you think it's good enough, could you please remove the downvotes? $\endgroup$ – Nautilus Jul 18 '15 at 7:34
  • 1
    $\begingroup$ +1: It seems like a [sound? intuitive?] proof to me. I don't believe that this answer is worthy of blame, after the explanation was added, especially considering that a diagonal is indeed the most efficient way to spread infection. $\endgroup$ – Conor O'Brien Jul 22 '15 at 17:44

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.