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.

Solution:

(a) r ⇒ p.

(b) p ⋀ ¬q ⋀ r.

(c) (p ⋀ q) ⇒ r.

(d) r ⇔ (p ⋁ q).

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!

Solution: log x < 0, for 0 < x < 1, so since both sides of the inequality “3 > 2” are being multiplied by the negative quantity log_{10}(1/2), the inequality in the second line should have been the reverse of the first line, that is, < instead of >.

(b) You are richer than you think:

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

Solution: $0.01 = $(0.1)^{2} ≠ ($0.1)^{2} because the units $^{2} and $ don’t match (just as in physics the difference between sec^{2} and sec indicates the difference between acceleration and velocity).

(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!

Solution:

The picture makes the little triangles look like isosceles triangles, but they aren’t. So when the two large pieces left after the little triangles are removed are slid together, they do not form a rectangle with the dimensions 11′′ × 10′′ × 1′′. Thus, the resulting rectangle is not the same as the original figure. (This illustrates why “proof by diagram” is mathematically suspicious.)

(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.

Solution: The polynomial 0x^{2} + 0x + 1 has no roots. The proof failed for this case since it divides by a, which is unsound when a = 0.

The polynomial x^{2} + 2x + 1 has only one root. For a ≠ 0, the algebra is ok, but the proof assumes that r_{1} ≠ r_{2}, which will be false when D = 0.

The proof is correct for polynomials with a ≠ 0 ≠ D (even though when D < 0, the meaning of \sqrt{D} is ambiguous). So these two conditions are required to make the claim correct.

(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.

Solution: The function

f(x) = \overbrace{x + x + … + x}^{x}

is defined only for nonnegative integers x. It is defined only on discrete points and is not continuous. Hence its derivative does not make sense.

(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!

Solution: The assumption that \sqrt{uv} = \sqrt{u}\sqrt{v} arises from our “common usage” of \sqrt{·} to be the positive square root. But this isn’t defined for the sqrt of a negative number (which is complex, so not positive or negative).

Problem 3 Generalize the proof that \sqrt{2} is irrational, e.g., how about \sqrt[3]{2}?

Solution: We prove that \sqrt[n]{2} is irrational. Proof by contradiction. Assume that \sqrt[n]{2} is rational. Under this assumption, there exists integers a and b with \sqrt[n]{2} = \frac{a}{b}, where a and b have no common factors (so that the fraction \frac{a}{b} is in lowest terms).

\sqrt[n]{2} = \frac{a}{b}

2 = \frac{a^{n}}{b^{n}}

2b^{n} = a^{n}

This means that a^{n} is even, implying that a is even. As a is even, a = 2c for some integer c. Thus,

2b^{n} = 2^{n}c^{n}

b^{n} = 2^{n−1}c^{n}

This means that b^{n} is even, implying that b must be even as well. Thus, the fraction, \frac{a}{b} was not in its lowest terms. This gives us our contradiction. Our original hypothesis, that \sqrt[n]{2} is irrational, is true.

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?

Solution: The answer is Yes.

Step 1. Divide into groups of 4 balls. Place two of these groups on two pans.

Two possible outcomes:

1. Equal. So the 8 balls that were weighed must be of the same weight, label them N (for “normal”) and one of the other 4 is of different weight, call them D.

Step 2. Place 3 D balls on one side and 3 N balls on the other side for the second weighing. Three possible outcomes again:

(a) Equal. The remaining D must be the ball of different weight.

(b) DDD side is heavier. So the ball of different weight is among these three and heavier. Now we can finish in one more weighing using the following approach: Place a ball on each pan of the balance. There are 3 possible outcomes:

i. The left pan is heavier. Then the ball in the left pan is the answer. ii. The right pan is heaver. Then the ball in the right pan is the answer. iii. The pans are equal. Then the third ball must be the heavy one.

(c) DDD side is lighter. Similar to previous case.

2. Not Equal. Call the heavier side balls H and the lighter side balls L. Then there are 4 H’s , 4 L’s and 4 N’s (the 4 that we didn’t weigh are of the same weight).

Step 2. Place 3 H’s and 1 L on one side and 1 H and 3 N’s on the other side for the second weighing. There are 3 possible outcomes:

(a) Equal. The ball of different weight is among the remaining 3 L’s and is lighter. We can find it in one more weighing.

(b) 3 H’s , 1 L side is heavier. Then one of the three H’s must be heavier than the rest. We can find it in one more weighing.

(c) 3 H’s , 1 L side is lighter. Then either the L on this side is lighter than the rest or the H on the other side is heavier than the rest. We can compare one of them with an N ball and find the ball of different weight!