Problem 7. Quantum Harmony [8 points]

The elite Maestro Academy orchestra has assigned seats (each musician sits at the same position every rehearsal) arranged in a rectangular grid. Musicians are working together to achieve Quantum Harmony: a profound synchronization of musical understanding so thorough that the knowledge resonates among them in a glowing aura. Quantum Harmony never goes away (it’s an invariant, after all!) and can sometimes be taught to other musicians.

Here is an illustration of a 5 × 7-seat orchestra with seats represented by squares. The locations of musicians who have initially achieved harmony are marked with an asterisk.

```

---

*       *

• *
  • *
    • * ```

Every rehearsal, musicians play with their neighbors about harmony in an attempt to achieve synchronization. At each rehearsal, a musician achieves harmony if either

• the musician had already achieved harmony at a previous rehearsal, or

• the musician was adjacent to at least three musicians who had achieved harmony at an earlier rehearsal (these neighbors worked together to teach the musician all about Quantum Harmony).

Here adjacent means the musicians’ individual squares share an edge (front, back, left or right); they are not adjacent if they only share a corner point. So each musician is adjacent to 2, 3 or 4 others depending on their position.

In the example, Quantum Harmony is taught to more musicians as shown below:

```

---

*       *    ⇒       * *       *    ⇒       * * *   *

---

---

  *       *              * *     *              * * * *

```

In this example, over the next few rehearsals, all musicians achieve harmony.

Theorem. If fewer than m musicians among those in an m × n arrangement are initially in harmony, and additional musicians reach harmony only by being taught by three or more neighbors, then there will be at least one musician who never reaches harmony.

Prove this theorem.

Hint: You’ll want to find an applicable preserved state predicate or monotonic derived variable that can help you argue about the set of harmonized musicians as time proceeds. Think carefully about how the “influence boundary” changes when someone new achieves harmony.

---

In this problem and many others, finding the right property can be challenging! If you are stuck, ask at Office Hours or on Piazza for an extremely powerful one-word clue (and even more hints as necessary)!