Lighting Up a Grid

This puzzle was sourced from an @algopuzzles tweet.

Here’s the puzzle:

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.