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.
Spoiler alert: lower bound.
- 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?