MathDB

Let a city be in the form of a square grid which has

n \times n

cells, each of which contain a skyscraper . At first the

m

skyscrapers burn, but the fire spreads: everyone skyscraper that has at least two burning neighboring houses (by neighboring houses we mean only houses that border the house along a street, not just at a corner) immediately gets fire. Prove that when in the end the whole city burns down, of must have been

m \ge n

.
[hide=original wording in German] Eine Stadt habe die Form eines quadratischen Gitters, welches n × n Zellen habe, von denen jede ein Hochhaus enthalte. Anfangs brennen m der Hochh¨auser, doch der Brand pflanzt sich fort: Jedes Hochhaus, das mindestens zwei brennende Nachbarh¨auser hat (unter Nachbarh¨ausern verstehen wir dabei nur H¨auser, die entlang einer Straße an das Haus angrenzen, nicht nur an einer Ecke), f¨angt sofort Feuer. Man beweise: Wenn am Ende die gesamte Stadt abgebrannt ist,muss m ≥ n gewesen sein.

Problem Statement