Filling a Grid with Good Neighbors

There is a number of chips placed in the squares of an N×N grid. We can add a chip to a square, provided it has at least two occupied 4-neighbors. The task is to position the chips initially so as to be able to fill the whole grid in a number of steps.

What is the least number of chips that are needed to complete the task?

The applet works this way: when the box "Set up" is checked, clicking on a grid square makes it occupied. It acquires color and a number 0 to indicated the step at which it was occupied. Clicking on an already occupied square sets it free. After forming an initial configuration to your satisfaction, check the "Play" box. This will enable the "One step" button. Clicking on that button expands the configuration by all possible neighbors. Each new square displays the number of the step on which it was added to the configuration.

What if applet does not run?

A few words

|Contact| |Front page| |Contents| |Algebra| |Activities| |Eye opener| |Store|

Copyright © 1996-2017 Alexander Bogomolny

The configuration of N chips placed on a diagonal will expand to fill the board. There are many more such configurations. The "diagonal" one is one of the fastest in the sense that it takes the least number of steps to fill the board, N-1. There are other configurations that do as well. It is interesting to find the slowest ones.

What if applet does not run?

Also, it may be shown that no configuration with fewer than N chips may expand to cover the entire grid. Try to prove that.

|Contact| |Front page| |Contents| |Algebra| |Activities| |Eye opener| |Store|

Copyright © 1996-2017 Alexander Bogomolny

 62055433

Search by google: