1.9 State Machines - Invariants

Chocolate Bars

We are given a chocolate bar with \(m \times n\) squares of chocolate, and our task is to divide it into \(mn\) individual squares. We are only allowed to split a chocolate bar using a vertical or a horizontal cut.

For example, suppose that the chocolate bar is \(3 \times 2\). A horizontal cut between the first and second rows of squares splits it into two bars, a \(1 \times 2\) bar and a \(2 \times 2\) bar. One cut of the \(1 \times 2\) splits it into individual squares, and three more cuts splits the \(2 \times 2\) bar into squares. So a total of 5 cuts splits the whole \(3 \times 2\) bar into squares.

At each step of the division process, let \(s\) be the number of splits already performed, and \(p\) the number of pieces of chocolate obtained.

  1. Which of the following predicates are preserved invariants for this process ?

    With each split, both \(s\) and \(p\) increase by 1; therefore, the first two predicates are preserved invariants. In contrast, the left side in the third predicate increases while the right side decreases.

  2. Which of the following quantities get smaller at each transition?

    Given a set of \(m\) and \(n\) (i.e., the size of the chocolate bar), \(mn\) does not change. With each split, both \(s\) and \(p\) increase by 1, \(mn-p\) decreases by 1, and \(p-s\) remains constant.

  3. What is the number of pieces of chocolate at the end of the division process?

    At the end of the process every square is separated, so \(p=mn\).

  4. What is the number of splits performed to reach the end of the division process?

    In Part 1, we found \(s=p-1\) a preserved invariant. This invariancy is also true at the beginning before the first split: \(s=0\) and \(p=1\). By the Invariant Theorem, the predicate \(s=p-1\) is true throughout the division process, thus, it is true at the end. From Part 3, we know that at the end \(p=mn\); substituting it into the invariant, we get \(s=mn-1\).