Massachusetts Institute of Technology Handout 5 6.042J/18.062J: Mathematics for Computer Science September 8, 2000 Professors Nancy Lynch and Shlomi Dolev

Tutorial 1 Problems

Problem 1 Let p, q, and r be the following propositions:

p : You get an A on the final exam.
q : You do every exercise in this book.
r :  You get an A in this class.

Write the following propositions using p, q, and r and logical connectives (e.g. ∨, ∧, ¬, ⟶).

(a) To get an A in this class, it is necessary for you to get an A on the final.

(b) You get an A on the final, but you don’t do every exercise in this book; nevertheless, you get an A in this class.

(c) Getting an A on the final and doing every exercise in this book is sufficient for getting an A in this class.

(d) You will get an A in this class if and only if you either do every exercise in this book or you get an A on the final.

Problem 2 Identify precisely what the bugs are in each of the following false proofs.

(a)

3 > 2
3 log_{10}(1/2) > 2 log_{10}(1/2)
log_{10}(1/2)^{3} > log_{10}(1/2)^{2}
(1/2)^{3} > (1/2)^{2}
Therefore, 1/8 > 1/4!

(b) You are richer than you think:

1c̸ = $0.01 = ($0.1)^{2} = (10c̸)^{2} = $1.

(c) Consider the following scheme to make millions. Obtain a slab of gold 10′′ × 11′′ × 1′′. Then cut out two little one-inch triangles at the corners. These triangles are the profit. Finally, slide the two slabs together again and note that the rectangle is now 11′′ ×10′′ ×1′′— the same size as it was before we removed the small triangles. By repeating the process, we can produce an unlimited supply of gold!

(d) Claim: Every polynomial p(x) = ax^{2} + bx + c over ℂ (the complex numbers) has two roots.

Sounds good, but the claim is false. Find the counterexamples and then restate the claim so it is correct.

Proof. Using the usual formulas for the roots of a quadratic, let

r_{1} ::= \frac{−b + \sqrt{D}}{2a}, and
r_{2} ::= \frac{−b − \sqrt{D}}{2a}, where
D ::= b^{2} − 4ac.

To verify that r_{1} is a root, note that

ar_{1}^{2} = a(\frac{−b + \sqrt{D}}{2a})^{2}
= a\frac{b^{2} − 2b\sqrt{D} + D}{4a^{2}}
= \frac{b^{2} − 2b\sqrt{D} + b^{2} − 4ac}{4a}
= \frac{2b^{2} − 2b\sqrt{D} − 4ac}{4a}
= \frac{b^{2} − b\sqrt{D} − 2ac}{2a}

and

br_{1} = b\frac{−b + \sqrt{D}}{2a}
= \frac{−b^{2} + b\sqrt{D}}{2a}

so

p(r_{1}) = r_{1}^{2} + br_{1} + c
= \frac{b^{2} − b\sqrt{d} − 2ac}{2a} + \frac{−b^{2} + b\sqrt{d}}{2a} + c
= \frac{−2ac}{2a} + c = −c + c = 0,

as claimed. A similar calculation confirms that p(r_{2}) = 0.

Handout 5: Tutorial 1 Problems 3 (e) What is wrong with the following proof that 2 = 1?

x^{2} = \overbrace{x + x + … + x}^{x}

Differentiating both sides with respect to x, we get

2x = \overbrace{1 + 1 + … + 1}^{x} = x

Hence 2 = 1.

(f) What is wrong in the following calculation?

1 = \sqrt{1}
= \sqrt{(−1)(−1)}
= \sqrt{−1}\sqrt{−1}
= \sqrt{−1}^{2}
= −1.
So, 1 = −1!

Problem 3 Generalize the proof that \sqrt{2} is irrational, e.g., how about \sqrt[3]{2}? Problem 4 You are given 12 identical looking balls, and told that one of them is of different weight from the other 11, but you don’t know in advance whether it is heavier or lighter. Can you find the ball that is of different weight using only 3 weighings on a balance scale?