21
$\begingroup$

As in this previous puzzle, we are again playing with our favorite bacteria, C. Coli, whose natural habitat is an 8x8 checkers board. These are very nasty bacteria - once they are in a cell of a checkerboard, that cell will be infected forever. They spread in a very peculiar way: Each night, at midnight, any cell with two neighbors infected by C. Coli will itself become infected. They are harmless to humans, except in large doses - if a whole checkerboard is infected and a human plays on it, they will suffer severe side-effects, including procrastination, prolonged consternation, and chronic cogitation (but any lesser dose is harmless).

The scientists at the lab know that their checkerboard has potentially been compromised and have agreed to make a grave sacrifice: They will not play checkers for the five weeks after the board was compromised. If every cell of their board is infected, they will discard it and apply for a grant to purchase another checkerboard. Otherwise, they will resume play (even if there was only one uninfected cell).

Given 8 samples of C. Coli, placed such that they will eventually infect the entire checkerboard, what is the longest amount of time it could take to infect the whole board? How can the bacteria be arranged to obtain this maximum? Is five weeks sufficient wait time to ensure that the board will never be fully infected?

(Bonus: Can you prove that the arrangement taking the maximal length of time is unique up to reflection & rotation?)

$\endgroup$
  • 5
    $\begingroup$ Those are pretty severe side-effects! :P $\endgroup$ – GentlePurpleRain Jul 17 '15 at 3:54
  • 1
    $\begingroup$ @GentlePurpleRain Imagine what the cube might do! Perhaps the twiddling of thumbs? $\endgroup$ – Conor O'Brien Jul 17 '15 at 6:58
  • $\begingroup$ Wait, what if we simply used the 8 queens configuration, would we not make it impossible for the board to get infected? $\endgroup$ – warspyking Jul 17 '15 at 13:11
  • $\begingroup$ Sounds like the max that can be on the board without entire infection is 8 (although it has nothing to do with the puzzle lol) $\endgroup$ – warspyking Jul 17 '15 at 13:12
  • 1
    $\begingroup$ @warspyking You can have $56$ cells infected without infecting the whole board - just put an infection on every cell except the first row. (And this is the maximum) $\endgroup$ – Milo Brandt Jul 17 '15 at 22:29
11
$\begingroup$

EDITED - thanks to @Meelo for pointing out my mistake.

We can do it in

38 days.

We place the C.Coli's at a4, a8, b2, c1, e2, g1, h3, h6.

Now we prove that this is optimal. Every day there are either 1 new infected cell or 2+ new infected cells. Let us have k days with single infections and l days with 2+ infections. Then k+2l<=56 and therefore k+l<=28+k/2. So, if we prove that k<=21, then the we can't do better than 38.

Let us assume that we have the ability to delay the infection of some cells for several days. Clearly, this will not reduce the number of days until the total infection. Notice that we can delay the infection in such way, so that it proceeds in 7 phases. At the beginning of phase i we start with 9-i fully infected rectangles and end with 8-i fully infected rectangles. Using the observation that the total perimeter of the infected area is a constant throughout, we can prove that:

  1. the width and the length of every rectangle have the same parity
  2. no two rectangles share a common edge
  3. for every pair of rectangles, there is at most one row/column, which intersects both of them.

During each phase two of the infected rectangles start a chain reaction, which causes them to infect a bigger rectangle, which contains both of them. The rest is just case analysis, counting the number of single infection days during the phases. If we combine two rectangles which are separated by 1 cell horizontally/vertically (i.e. there is a row column, which intersects both rectangles), then the corresponding phase will contain at most 3 single infection days. In order to have 4+ single infection days during a phase, we must combine two rectangles which share common vertex, one of which has dimensions with difference 4 or more and the other one is a single cell. The only options are if the dimensions of the disproportional rectangle are (1,5), (2, 6), (3,7), (1,7). All of these options are easy to examine, can add some more details if needed.

$\endgroup$
  • $\begingroup$ I also independently got 37 days, although now it appears I had a rotation and a reflection of your first board $\endgroup$ – qwertylpc Jul 17 '15 at 13:13
  • 1
    $\begingroup$ Another 37 days solution: A1, A7, B3, C1, C5, D8, F1, H8 $\endgroup$ – qwertylpc Jul 17 '15 at 15:06
  • $\begingroup$ This was exactly the first arrangement I thought to be optimal (but I later discovered a 38 day solution & proof). If I'm reading your proof correctly, the hole is that the premise that each stage has at most 3 days where only one cell is infected - in the 38 day solution, there are two stages in which there are 4 days where only one cell is infected. You're on the right track though, I think. (To see this yourself without giving away the answer, here's a 37 day solution which has such a stage: A2, B1, D2, F1, G3, A5, H6, A8) $\endgroup$ – Milo Brandt Jul 17 '15 at 22:23
  • $\begingroup$ Yeah @Meelo, my bad. Found a 38 solution, will look for the proof later tonight. $\endgroup$ – Puzzle Prime Jul 17 '15 at 22:42
  • $\begingroup$ Could you add a picture/diagram of the starting positions? $\endgroup$ – JonTheMon Jul 22 '15 at 19:34
14
$\begingroup$

Not exactly answering this question, but given 9 infections still on an 8x8 board, it is actually possible to delay the inevitable until 40 days. Pretty counter-intuitive huh?

Locations are A1, A5, A8, B3, B7, D1, E8, G1, H8

Also, I believe that this is the maximum for an 8x8 board with any number of initial infections.

As for the edges argument I made for the preceding question here, you'll notice with 9 initial infections, we must lose a total of 4 edges. This is accomplished by losing 2 edges on the 19th day, and the 34th day along the bottom row.

$\endgroup$
4
$\begingroup$

The maximum length of time to infect the entire board from $8$ cells is $38$ days and the only arrangement achieving this maximum is as follows (where the $X$'s are infected cells):

--X--X--
X-------
--------
-X------
--------
X-------
-X------
---X---X

Our process can be described as starting with a $2\times 2$ square and adding new cells to enlarge it one step at a time, each time increasing the area's perimeter by $4$. In particular, we start with a square:

X-
-X

which will be infected after $1$ day. We then increase the height of the square by two, placing a new infection such that, once the corner (the last cell infected) of the previous image is infected, the new infection will take effect. In particular, we get:

-X
--
X-
-X

Infecting this takes $3$ days. We then increase the height again in a similar manner yielding:

X-
--
-X
--
X-
-X

Taking $3$ more days. Then, we increase "diagonally", incrementing both height and width:

--X
X--
---
-X-
---
X--
-X-

This takes $6$ days. Then we increase diagonally this again, noting that the last cell filled above is the bottom right corner:

--X-
X---
----
-X--
----
X---
-X--
---X

This takes $7$ days. Then, finally, we increase the width, noting that the top right is the last infected piece, to get:

--X--X
X-----
------
-X----
------
X-----
-X----
---X--

which takes $9$ days to be infected. Then, we increase the width again yielding the correct answer and taking an additional $9$ days. All told, the process will take $38$ days. Moreover, having decided on the sequence of increases to width/height/diagonal, we never had any choice in where to place the infections (up to symmetry) as we always had to put the new infection two cells away from the last infected square of the previous arrangement in a specified direction - once we have shown that the general process generating this answer is optimal, this suffices to show uniqueness of the solution.


Act One: Conclusions Are Proven From Intuitive Assumptions

We will start by taking the following lemma (whose more difficult proof comprises Act Two of this post) and deducing that our construction is optimal. We assume we are on an $n\times n$ board, as our solution generalizes naturally.

The best solution is to start with a $2\times 2$ square, and then add infections such that each successive infection is placed to create a rectangle (of perimeter $4$ larger) with all the previous infections.

In particular, we will describe our above solution as the string: $$[2\times 2]YYDDXX$$ meaning "start with a $2\times 2$ square, increase its height twice ("Y"), increase it diagonally twice ("D"), then increase its width twice ("X"). After three steps, we could describe the position as $$[2\times 4]YDDXX$$ as we would have a $2\times 4$ rectangle.

We notice that $[a\times b]X$ will become $[(a+2)\times b]$ after at most $b+1$ days, that $[a\times b]Y$ will become $[a\times (b+2)]$ after at most $a+1$ days and $[a\times b]D$ will become $[(a+1)\times (b+1)]$ after at most $\max(a,b)$ days.

Moreover, we may assume that $a\leq b$ at all times using the symmetries of the problem - in particular, we may assume that, if we start from a square rectangle, then we can exchange every instance of $X$ with $Y$ and vice versa, since the problem clearly has that symmetry (so we should never see the pattern $[a\times a]X\ldots$). This lets us assume that, whenever we have a square of infection, our next move will be $Y$ or $D$ - since if it were $X$, we could exchange all further $X$'s and $Y$'s and get an equivalent length of time. Thus, we may assume $[a\times b]D$ takes $b$ (rather than $\max(a,b)$) days to become $[(a+1)\times (b+1)]$.

Then, we simply notice a few facts to reduce this to a one-variable optimization problem rather than optimization over a space of strings:

  • $[a\times b]XY$ and $[a\times b]YX$ take equally much time, so we can freely swap their order; without loss of generality, let us assume that the pattern $XY$ never appears (and is always replaced by $YX$).

  • $[a\times b]XD$ is always slower than $[a\times b]DX$.

  • $[a\times b]DY$ is always slower than $[a\times b]YD$.

Using the above, we may conclude that the slowest string of enlargements must have the form*: $$[2\times 2]\underbrace{YY\ldots YY}_{y\text{ times}}\underbrace{DD\ldots DD}_{d\text{ times}}\underbrace{XX\ldots XX}_{x\text{ times}}$$ where we must satisfy $2y+d=n$ and $2x+d=n$ - implying $x=y$ and $d=n-2y$, which reduces this to a one variable optimization problem. In particular, each of the beginning $Y$'s will take $3$ days for the enlargement. The first $D$ will take $2y+2$ days and the last will take $n-1$ days, so they will in total take $$\sum_{i=2y+2}^{n-1}i=-2y^2 - 3y - 1 +\frac{n^2}2 - \frac{n}2.$$ Then, each $X$ will take $n+1$ days, so they will in total take $y(n+1)$ days. Putting this all together (plus one day for the $2\times 2$ pattern) yields that the length of time taken by the above pattern with $y$ instances of $Y$ will be: $$-2y^2 + (n+1)y + \frac{n^2}2 - \frac{n}2$$ which is convex, has a maximum at $\frac{n+1}4$ and is symmetrical about that point. Thus, the nearest integer to $\frac{n+1}4$ maximizes that. So, for $n=8$, we get that $y=2$ (rounded from $\frac{9}4$) is optimal, and the above expression yields $38$ as the upper bound at that point. In particular, we can find the optimal solutions for all $n\geq 4$ as:

If $n$ is between $4c-3$ and $4c+1$, then an optimal solution is to enlarge upwards $c$ times, then diagonally $n-2c$ times, and then rightwards $c$ times. (If $n$ is not $1$ mod $4$, this $c$ is unique).

Similar methods apply to a $n\times m$ square with $n\leq m$, where $n+m$ is even and we have $\frac{n+m}2$ infections).


Act Two: We Replace Our Intuition with Mathematical Contortionism

Unfortunately, it takes a lot more machinery to prove that our lemma was correct than it does to apply it - in particular, as natural as it is to talk about rectangles, this structure is not implicit in the update rule of our automata, yet we need to apply the model as an upper bound nevertheless. Firstly, we need to define what these rectangles are. Our goal is to, for any infection, create a binary tree of rectangles, such that each node is the rectangular infection generated by combining the rectangles of its two children nodes, and then to characterize the length of an infection based on the properties of this tree. We do not directly construct such a tree, but it is implicit in the induction we use, and the major lemma used in this section may be used to construct it.

In particular, let us begin with the following definition:

Let $S$ be a finite subset of $\mathbb Z^2$. Define $\newcommand{\cl}{\operatorname{cl}}\cl(S)$ to be the set of points eventually infected if those in $S$ are infected.

It should be clear that $\cl$ is a closure operator. Moreover, the closed sets with respect to this operation (i.e. sets such that $\cl(S)=S$) are exactly those from which no new infections are possible - we may characterize these as follows:

A set $S$ is closed if and only if it a union of rectangles, no cell being adjacent or contained in more than one rectangle.

Now, to build our tree of infections, we use the following important lemma:

For all $S$ with more than one element such that $\cl(S)$ is a rectangle, there exists a disjoint pair $A,B\subseteq S$ such that $\cl(A)$ and $\cl(B)$ are rectangles neither equal to $\cl(S)$ and that $\cl(A\cup B)=\cl(S)$.

To prove this, consider the set of rectangles other than $\cl(S)$ which are closures of subsets of $S$. This is obviously finite and non-empty if $|S|>1$. Therefore, ordered by inclusion, there is a maximal element $\cl(A)$ - a rectangle not contained by any other such rectangles. Set $B=S\setminus \cl(A)$. Now, suppose that $\cl(B)$ is the union of rectangles $\cl(B_1),\cl(B_2),\ldots,\cl(B_k)$. Notice that $\cl(A\cup B_i)$ must strictly contain $\cl(A)$. It is therefore either equal to $\cl(S)$, in which case we're done, or it is not a rectangle. If none of the $B_i$ have that $\cl(A\cup B_i)$ was a rectangle, then it would be the case that no cell could be adjacent to $\cl(A)$ and a $\cl(B_i)$ (nor to distinct $\cl(B_i)$ and $\cl(B_j)$), implying that $\cl(A)\cup\cl(B_1)\cup \cl(B_2)\cup\ldots\cup \cl(B_k)$ was a closed set containing $S$ which was not a rectangle, contradicting that $\cl(S)$ is a rectangle. Thus, one of the $B_i$ must satisfy the conditions of the lemma. (If $S$ has that its perimeter and it's closure's perimeter are equal, we may easily modify the above proof to show that $A$ and $B$ can and must be a partition of $S$)

Using this tree, we may bound the length of time it takes for the infection to complete its spread. In particular, let $t(n,m)$ be the maximum length of time it takes to infect all the corners of an $n\times m$ rectangle with $\frac{n+m}2$ initial infections, where $n+m$ is even. This equals the amount of time to infect the whole square for $n,m>1$, since all the possible combinations of rectangle infect a corner last and only begin once both sub-squares have their corners infected. Notice that there are only $3$ manners of combining two rectangles such that the result has the sum of their perimeters - on two $2\times 2$ rectangles, we illustrate them as follows:

-XX
-XX
---
XX-
XX-

--XX
--XX
XX--
XX--

---XX
XX-XX
XX---

Which correspond to increasing the height, the diagonal, and the width. In particular, to make an $n\times m$ rectangle ($n,m>1$), one must choose one of five options. For the first $3$, suppose that $x_1,x_2,y_1,y_2$ are positive integers with $x_1+y_1$ and $x_2+y_2$ both even. We are combining rectangles $x_1\times y_2$ and $x_2\times y_2$ in one of the above manners, letting $T=\max(t(x_1,y_1),t(x_2,y_2))$.

  • Combining in the first manner (heightwise). We require $x_1+x_2=n+1$ and $y_1+y_2=m-1$ and $x_1,x_2>1$. This takes $T+\max(x_1+y_2,x_2+y_1)$ days.

  • Combining in the second manner (diagonally). We require $x_1+x_2=n$ and $y_1+y_2=m$. This takes $T+\max(x_1+y_2,x_2+y_1)-1$ days.

  • Combining in the third manner (widthwise). We require $x_1+x_2=n-1$ and $y_1+y_2=m+1$ and $y_1,y_2>1$. This takes $T+max(x_1+y_2,x_2+y_1)$ days.

  • Increasing height only. $x_1=1$ and $x_1+x_2=n+1$ and $y_1+y_2=m-1$. This takes $T+x_2+y_1$ days.

  • Increasing width only. $y_1=1$ and $x_1+x_2=n-1$ and $y_1+y_2=m+1$. This takes $T+x_1+y_2$ days.

Which, taking $t(1,n)=t(n,1)=0$, yields a recurrence relation for $t$ allowing explicit computation. However, even better than that, we can show that the first three options are never optimal, hence we only use the last two options - but moreover, those options are obviously slowest when $x_1=y_1=1$, meaning we should always enlarge rectangles according to the previously used procedure.

To prove this, assume without loss of generality that $t(x_1,y_1)\leq t(x_2,y_2)$ - so essentially, the creating of the first rectangle comes for free, since it was done in parallel with the second rectangle. For the first (and by symmetry, the third) case, suppose we instead of joining a $x_1\times y_1$ rectangle to the $x_2\times y_2$ one, we increase the height of the $x_2\times y_2$ rectangle with a $1\times 1$ square placed above it, and then diagonally join the resulting $x_2\times (y_2+2)$ rectangle to a $(x_1-1)\times (y_1-1)$ rectangle**. That is, we consider the alternate diagram:

--X
-X-
---
XX-
XX-

This takes a total of $T+[x_2+1]+[\max(x_1-1+y_2+2,x_2-1+y_1)-1]$ which is at least as long as before. Similarly, when combining rectangles diagonally, we instead join a $1\times 1$ rectangle to the $x_2\times y_2$ one and then join the $(x_1-1)\times (y_1-1)$ one to that. We find a similar result algebraically.

The above suffices to show the desired claim that the optimal solution is of the form claimed, implying the displayed solution is optimal and unique for a $8\times 8$ board.

(*If we we're being very careful, we would note that all of the exchanges suggested, including exchanging all $X$'s and $Y$'s after something of the form $[a\times a]X\ldots$, decrease the lexicographic order of the string when we take $Y<D<X$. Thus, we will eventually reach a minimal element if we greedily apply such swaps - and in this context, a minimal element is one in which no such swaps are possible and is of the given form)

(**Some special care needs to go into the $y_1=1$ case, but the result comes out the same. A similar exception presents itself so for the diagonal combination)

$\endgroup$
  • 1
    $\begingroup$ Gosh, I wouldn't have written this post if I'd known a priori that Act Two was going to be such a marathon! $\endgroup$ – Milo Brandt Jul 18 '15 at 23:38
3
$\begingroup$

Oops! Turns out that I didn't get the answer, but here was my thought process anyways:

Given 8 samples of C. Coli on an 8x8 board, it will take at most:

28 days to infect the entire board. Thus waiting 5 weeks (35 days) is sufficient to determine if the board is fully infected or not.

TL;DR solution: The slowest rate of growth possible is 2 squares a night: $(64-8)/2 = 28$ nights to fully infect the board.

Full answer: An uninfected square will become infected if it is surrounded on at least two sides by infected squares. In order to completely flood the board, each sample must occupy an unique row and column on the board (see proof below). There are many ways to do this. For example we can put them all on the diagonal. However, this leads to an infected board in 7 days! So to minimize growth we want to keep each sample as far away from the sample above and below it. Thus leading to a configuration like:
C . . . . . . .
. . . . . . . C
. C . . . . . .
. . . . . . C .
. . C . . . . .
. . . . . C . .
. . . C . . . .
. . . . C . . .
After the first night, the bottom two samples are close enough to infect two more cells:
C . . . . . . .
. . . . . . . C
. C . . . . . .
. . . . . . C .
. . C . . . . .
. . . . . C . .
. . . C C . . .
. . . C C . . .
Notice, that the addition of the new cells produce a square of infected cells that has a corner touching the next sample in the row above. We continue to night number two:
C . . . . . . .
. . . . . . . C
. C . . . . . .
. . . . . . C .
. . C . . . . .
. . . . C C . .
. . . C C C . .
. . . C C . . .
We infected two more cells! Notice that the new configuration does not form a square, and therefore does not have a corner touching the next sample in the row above! Taking this pattern, we see that the rate of growth is two cells every night. Thus it will take at most $(64-8)/2 = 28$ nights to fully infect the board.
Lemma 1: was going to complete a proof for this, but it turns out that this assumption was wrong so I can't actually prove it haha.

$\endgroup$
  • 3
    $\begingroup$ This is a cool construction! But, you say "In order to completely flood the board, each sample must a unique row and column". This is not true. $\endgroup$ – Mike Earnest Jul 17 '15 at 4:34
  • 1
    $\begingroup$ Also there are most definitely days in which you can only infect a single cell. $\endgroup$ – qwertylpc Jul 17 '15 at 12:32

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.