Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Need help starting a proof about an infinite square grid.

  1. Jun 19, 2011 #1
    Hi, I need help with simply starting to prove this. I'm terrible with proofs and even the easy ones are hard for me. Any tips to get started in the right direction would be appreciated.

    A city represented by an infinite square grid of blocks is on fire. Every day, the status of city block is either burned or okay. Due to winds from the northeast, the status of a city block on Day i is the majority of the statuses of (1) that block, (2) its immediate northern neighbor, and (3) its immediate eastern neighbor from Day i - 1. Prove the following claim: If on Day 0 there are only n okay blocks remaining in the city, the entire city will be burned by Day n + 1.
  2. jcsd
  3. Jul 19, 2011 #2
    I notice this was your first post, so hello and welcome to PF!

    Now, I know you are anxious to prove this statement, but first I propose you think about a few questions.

    First, since there are [itex]n < \infty[/itex], what would the best possible layout for those n blocks be--grouped, spread out, partially grouped, etc? Moreover, is their a worst-case for the best case scenario (this one specifically deals with [itex]n[/itex] specifically.

    Next, is it possible for all of the [itex]n[/itex] blocks to have an "okay" neighbor to the north and to the east?

    Finally, how many cases do you think you need to consider--is it possible to prove this by considering only 1 case?

    All of these questions have answers so hopefully after you think about them and we talk you will not only have an idea where to start, but also how to prove it.

    I look forward to what you think about these.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook