2 Invariants

2 Invariants
Props A chocolate bar
5 paper cups
• An invariant is something that does not
• Other names you may be more familiar with
are laws, patterns.
Invariants in Maths and Science 1
Invariants are fundamentally important.
Maths 2.PI.radius = circumference
(or 2.PI.R – C= 0)
Chemistry H2 + O = H2O
(hydrogen + oxygen = water)
Conservation of mass
Invariants in Maths and Science 2
• In Physics
• Conservation of energy (e.g. vertical
• Conservation of momentum (e.g. billiard balls)
• Conversation of angular momentum (e.g.
skater or person on swivel office chair).
• Conservation of charge, lepton number,
baryon number.
Chocolate Bars
• A rectangular chocolate bar is
divided into chunks by horizontal
and vertical grooves.
• It is to be cut into individual
• A cut is made by taking a piece
and cutting along a groove. This
splits a piece into two pieces.
• How many cuts are needed.
How do we describe the state of the problem
Two variables.
P = number of pieces of chocolate
C = number of cuts
P and C describe the state of the chocolate bar
This description removes detail (e.g. it is
chocolate, the order the cuts are made).
Model the cutting action / process
P, C := P+1, C+1
:= is read as “becomes”
This describes a change of state (like before
and after)
• NOTATION WARNING (==, = , :=)
• Invariant is P-C (show working on board)
Initially P=1 and C=0
So initially P-C=1
But P-C is invariant
When the bar is cut into S squares, P=S
S-C=1, that is C=S-1
The number of cuts required is one less than
the number of pieces
Tumbler Problem
• Several tumblers (cups or classes) are placed
on a table. Some are the right way up, some
are upside down. You can only turn over a pair
of tumblers. You cannot turn over an
individual tumbler (that would make the
problem trivial). The aim/goal is to turn all the
tumblers the right way up.
Abstraction, Assignment
• U is the number of tumblers upside down
• (this does not record the position of the
• 3 cases
• 1 turn two tumblers the right way up (U:=U+2)
• 2 turn two tumblers the wrong way up (U:=U-2)
• 3 turn one the right way up and the other the
wrong way up (U:=U+1-1)
• What is an invariant of these 3 assignments?
Invariant - Parity
Parity is a Boolean value (true or false)
True if (0, 2, 4, 6, …)
False if (1, 3, 5, 7, …)
Notation even.U
Invariant of U:=U+2 (show this)
Invariant of U:=U-2 (show this)
Modular arithmetic
• even.U is an invariant of the problem
• no matter how many times we turn over pairs
of tumbler, the value even.U will not change
• Invariant – something that does not change
• Abstraction – remove unnecessary detail and
focus on the essential parts of the problem
• Chocolate bar – the difference P-C was
• Inverting tumblers – the parity was invariant.
Next Lecture
• River crossing problems
• Outline fox chicken grain

similar documents