Le Monde puzzle [#1141]

This article is originally published at https://xianblog.wordpress.com

The weekly puzzle from Le Monde is in honour of John Conway, who just passed away, ending up his own game of life:

On an 8×8 checker-board, Alice picks n squares as “infected”. She then propagates the disease by having each square with least two infected neighbours to become infected as well. What is the minimal value of n for the entire board to become infected? What if three infected neighbours are required?

A plain brute force R random search for proper starting points led to n=8 (with a un-code-golfed fairly ugly rendering of the neighbourhood relation, I am afraid!) with the following initial position

With three neighbours, an similar simulation failed to return anything below n=35 as for instance:

oops, n=34 when running a little longer:

which makes sense since an upper bound is found by filling one square out of two (32) and adding both empty corners (2). But this upper bound is only considering one step ahead, so is presumably way too large. (And indeed the minimal value is 28, showing that brute force does not always work!)

Thanks for visiting r-craft.org
This article is originally published at https://xianblog.wordpress.com
Please visit source website for post related comments.