After the water has boiled, it takes 5 minutes to perfectly cook an egg. Unfortunately, we only have 2 hourglass timers:
one for 3 minutes and one for 4 minutes. How can we possibly time 5 minutes using only the 2 timers?
There's no way to obtain a 5-minute total using one timer after the other. To get 5 minutes, start both timers at once.
After 3 minutes, there will be 1 minute left in the 4 minute timer. Put the egg in the water and flip the 4-minute timer
once the 1-minute timer has elapsed.
Remark: other versions of this problem use different numbers like 11 and 7. It turns out that we can time any number of
minutes with just these 2 timers!
Definition: consider any 2 integers a, b. We say that "a divides b" if and only if there exists an integer q such that b = q*a.
We write this symbolically as
We might also say that "a is a factor of b" or that "b is a multiple of a".
If no such q exists, then a does not divide b, and we write
E.g. Evaluate as true or false:
Let a, b, c be integers
(i) if a|b and b|c then a|c (transitivity)
(ii) if a|b and a|c then a|(bx + cy) for any integers x, y
(iii) if a|b and b|a then a=±b
January 29, 2016
Lecture Notes Page 1