Lighting Up a Grid

This puzzle was sourced from an @algopuzzles tweet.

Here’s the puzzle:

On an nxn grid a few nodes are set on fire at t=0. The fire spreads like this: if at least two neighboring nodes of node x are lit, then node x will also catch fire in the next time step. What's the minimum number of nodes that have to be lit to burn the entire grid?#exportober

— Algorithmic Puzzles (@algopuzzles) October 18, 2021

Here’s an argument for the lower bound by Harshil Mittal.

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

At any time 0 \leq t \leq T,

• For every lit node (i,j), let f(i,j,t) denote the number of edges of the node (i,j) that are not shared with another lit node.

• Let g(t) denote the sum of f(i,j,t) over all lit nodes (i,j)

We show that g(t+1) \leq g(t) for all 0 \leq t \leq T-1.

Let 0 \leq t \leq T-1. Let (u,v) denote the new node which is lit up at time t+1. Let X denote the set of all lit neighbors of (u,v) at time t. For every node (i,j) in X, we have f(i,j,t+1) = f(i,j,t) - 1. Also, note that f(u,v,t+1) = 4-|X|. Therefore, g(t+1) = g(t) - |X| + (4-|X|) = g(t) + 4-2|X|. So, as |X| \geq 2, we get g(t+1) \leq g(t).

Now, we have 4n = g(T) \leq g(0) \leq 4p. Thus, n \leq p, as desired.