I asked the year 6 (10- and 11-year-olds) children I teach through Code Club if they could find the five cell pattern that kept a Game of Life board going indefinitely (ie., could they find the “glider” pattern?).
Their prize if they manage it in the next week is chocolate. Of course they could look it up on the Internet – and I won’t object if they do, because they will still have shown intelligence in piecing together the clues.
But what if they search for solution in some algorithmic way? (Actually one of them already sent me an answer which was quite close to correct but was actually a sort of “Methuselah” pattern which filled the screen with living cells before reaching a stasis after about 115 generations.)
Well the first thing they could do is just plonk down 5 counters at random on the board and see if one of these patterns was the correct one. Let’s say they approach this totally randomly and – on average – it takes a minute to determine if the solution is correct or not.
There are obviously possible solutions (this is the binomial coefficient/expansion – we are picking 5 spots at random from 400 possible spots as the board has a 20 x 20 grid) – this is which is approximately – so using this method would take around the known age of the universe, give an order or two, to find the solution.
So, if we did this by checking cells which were, at most, one cell away from a previous cell? (The work below is my own, I think it’s right!)
Well the first cell could be anywhere, the location does not matter : 1
The second cell could then be in one of eight positions: 1 x 8
The third cell could then be in one of twelve positions: 1 x 8 x 12
The fourth could then be in one of sixteen positions: 1 x 8 x 12 x 16
And the fifth could then be in one of twenty positions: 1 x 8 x 12 x 16 x 20
This would take a mere 30,000 minutes or so to check: a good three weeks or so of continuous work.
- cellular automata (cyberleague.wordpress.com)