Unorthodox Farmers

Logic Level 3

64 farmers each have square farms arranged in an 8 $\times$ 8 grid. The farmers all want to grow crops. If on one day a farmer is not already growing crops, then the next day s/he will start growing crops if at least two of his/her adjacent neighbors are already growing crops . (Note we mean adjacent by a side, not a corner.)

If on some day the 8 farmers on a diagonal are all growing crops, eventually (after 7 days) all farmers will be growing crops. If on some day exactly 7 farmers are growing crops, is it possible that eventually all farmers will be growing crops?

This problem is not original.

Yes for several distinct choices of 7 farmers but not all. No. No, but it is possible on a 9x9 grid when exactly 8 farmers are growing crops. Yes, and it doesn't matter which 7. Yes, but only for one choice of 7 farmers up to symmetry.

2 solutions

Maggie Miller
Jul 16, 2015

Let $P$ be the perimeter of the area $A$ in which crops are growing.

If a farmer with exactly two neighbors in $A$ joins $A$ , then $P$ doesn't change.
If a farmer with exactly three neighbors in $A$ joins $A$ , then $P$ decreases by $2$ .
If a farmer with exactly four neighbors in $A$ joins $A$ , then $P$ decreases by $4$ .

Therefore, each day $P$ will decrease or stay the same. If we start with $7$ farmers growing crops, $P$ is originally at most $4\times 7=28$ . When all farmers are growing crops, $P=32$ . Since $P$ cannot increase, it is impossible for all farmers to eventually grow crops if originally only $7$ are originally growing crops.

Thus, the answer is No .

(Note this argument extends similarly to the $9\times 9$ case.)

An oldie, but a goodie.

Daniel Liu - 5 years, 11 months ago

A very interesting problem which on the surface looks as if we should analyze the area instead of the perimeter.

William Nathanael Supriadi - 4 years, 8 months ago

is this in any way related to game of life?(https://en.wikipedia.org/wiki/Conway%27s Game of_Life)

Ajinkya Shivashankar - 4 years, 7 months ago

Dean Menezes
Jul 16, 2015

The perimeter is nonincreasing.

Unorthodox Farmers

This problem is not original.

2 solutions

0 pending reports