Lighting up a grid

Lighting up a grid

This puzzle is about finding the optimal way to set a grid on fire. The question was posed by @algopuzzles on Twitter:

Spoiler alert: upper bound.

You can check that lighting up the diagonal is enough, so is an upper bound.

Spoiler alert: lower bound.

Harshil made the following argument for a lower bound:

Consider an arbitrary but fixed solution. Let denote the number of nodes that are lit up at time 0. Let denote the time taken to lit the entire grid. WLOG, assume that for each , exactly one new node is lit up at time .

At any time

  • For every lit node , let denote the number of edges of the node that are not shared with another lit node.
  • Let denote the sum of over all lit nodes .

We show that for all .

Let . Let denote the new node which is lit up at time . Let denote the set of all lit neighbors of at time . Then we have the following observations:

  • For every node in , we have .
  • Also, note that .
  • Therefore, .
  • So, as , we get .

Now, we have . Thus, , as desired.

Followup comments:

  • It was conjectured that every solution "looks" like a permutation matrix. We do have examples to show that there are permutation-matrix-like configurations where the fire does not spread at all. Are there solutions that place light up more than one cell in a row or column?
  • Count the number of solutions. More generally, given a number between and , how many configurations with nodes lit up are such that they will eventually leave t nodes on fire?
  • Make a JavaScript-based web interactive that people can play with :)

super-embed:<div id="hyvor-talk-view"></div><script async defer type="text/javascript" src="//talk.hyvor.com/web-api/embed.js"></script>