13 Aug 2016

School

Department

Course

Professor

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?

Solution

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!

Divisibility

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:

Proposition:

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

Lecture 11

January 29, 2016

10:33 AM

Lecture Notes Page 1