Problem #DES-InvariantsLvl2

Descriptions

Problem

Today we will learn a really useful strategy for solving a certain kind of problems. This strategy is called the invariance principle, and after working through this sheet you’ll be able to recognise easily when we need to use an invariant to solve a problem. This strategy is applicable to kinds of problems where some task is repeatedly performed, and we wish to see if it is possible to transform our “initial state" into some given “final state". We will see by solving these problems, that sometimes we can identify a property of our setup that never changes after this repeated task is performed. Such a property is called an invariant. Sometimes however, we can identify a property that does change, but always changes in the same way. These are called monovariants (the prefix “mono" comes from Greek, meaning “one", i.e: monovariants are quantities that change in one particular way). Let’s check out some examples to see these concepts in practice.