# 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.

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