The firefighter problem is a monotone dynamic process in graphs that can be viewed as modeling the use of a limited supply of vaccinations to stop the spread of an epidemic. In more detail, a fire spreads through a graph, from burning vertices to their unprotected neighbors. In every round, a small amount of unburnt vertices can be protected by firefighters. How many firefighters per turn, on average, are needed to stop the fire from advancing? We prove tight lower and upper bounds on the amount of firefighters needed to control a fire in the Cartesian planar grid and in the strong planar grid, resolving two conjectures of Ng and Raff.
We solve Conway's Angel Problem by showing that the Angel of power 2 has a winning strategy. An old observation of Conway is that we may suppose without loss of generality that the Angel never jumps to a square where he could have already landed at a previous time. We turn this observation around and prove that we may suppose without loss of generality that the Devil never eats a square where the Angel could have already jumped. Then we give a simple winning strategy for the Angel. In the quarter of a century since three mathematicians and game theorists collaborated to create Winning Ways for Your Mathematical Plays, the book has become the definitive work on the subject of mathematical games. Now carefully revised and broken down into four volumes to accommodate new developments, the Second Edition retains the original's wealth of wit and wisdom. The authors' insightful strategies, blended with their witty and irreverent style, make reading a profitable pleasure. In Volume 4, the authors present a Diamond of a find, covering one-player games such as Solitaire. We solve the Angel Problem, by describing a strategy that guarantees the win of an Angel of power 2 or greater. Basically, the Angel should move north as quickly as possible. However, he should detour around eaten squares, as long as the extra distance does not exceed twice the number of eaten squares evaded. We show that an Angel following this strategy will always spot a trap early enough to avoid it. We show that in the game of angel and devil, played on the planar integer lattice, the angel of power 4 can evade the devil. This answers a question of Berlekamp, Conway and Guy. Independent proofs that work for the angel of power 2 have been given by Kloster and by Mathe.  