Report

2 Invariants Props A chocolate bar 5 paper cups Invariants • An invariant is something that does not change. • 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 projectile) • 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 squares. • 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. Abstraction • • • • • • 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). Assignments • • • • 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) Induction • • • • • • 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 tumblers) • 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 Solution • 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 Review • 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 invariant • Inverting tumblers – the parity was invariant. Next Lecture • River crossing problems • Outline fox chicken grain