Problems(1)
Let a city be in the form of a square grid which has n×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≥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. combinatorics