Mfcttrf

The cubicle farm at the Colla-R water treatment plant is laid out in a neat square: eight rows of eight cubicles with a narrow corridor between each cubicle (in the diagram the thin black lines are the corridors). Each cubicle is currently occupied by an employee, and no employees are on holiday.

The cubicles identified by being coloured red have ill employees in them: they have contracted some water-borne illness and are infectious. Due to the layout of the cubicles, a healthy employee only contracts the illness if they have two ill immediate neighbours in the four cardinal compass directions (you may take North to be pointing upwards relative to the page). For example, the cubicle at the end of the second row from the top contains an employee who is about to become ill. Ill employees do not go home, do not recover, are not allowed to leave their cubicle, but (luckily for them) do not die. As per company policy, the Colla-R HR department have now quarantined the cubicle farm, and no employee may leave until either everyone is ill, or everyone is well.

If, at the start of each hour, any healthy employee who has two ill neighbours as described becomes ill and immediately infectious, will all the employees fall ill? If not, what is the minimum number and location of ill employees that would ensure they do all fall ill? (The Colla-R HR department would of course like to avoid this happening.)

Answer 1

No, they will not all fall ill. In particular, none of the employees in the top (or bottom) row will fall ill as they need to have at least one infected neighbour in the same row. Since none are ill in the beginning, none will become ill.

Suggestion for the minimum

If all of the cubicles on a diagonal have ill employees then everybody will eventually fall ill. So this gives an upper bound of 8 for the minimum.

Proof that this is the minimum

One important thing to notice is that the total perimeter of the ill area never increases (this is due to the fact that the two cubicle walls providing the infection get absorbed into the infected area in the next step producing, at most, two new cubicle walls to the infected perimeter).

Now, suppose there are just $7$ ill employees. Then, the total infected perimeter is at most $4 times 7 =28$. This can never increase, hence, the infection cannot cover all employees since the total perimeter is $32$.