Page 129 - Discrete Mathematics and Its Applications

108 1 / The Foundations: Logic and Proofs

Exercises

n
2
1. Prove that n + 1 ≥ 2 when n is a positive integer with 18. Show that if r is an irrational number, there is a unique
1 ≤ n ≤ 4. integer n such that the distance between r and n is less
2. Prove that there are no positive perfect cubes less than than 1/2.
1000 that are the sum of the cubes of two positive integers. 19. Show that if n is an odd integer, then there is a unique
integer k such that n is the sum of k − 2 and k + 3.
3. Prove that if x and y are real numbers, then max(x, y) +
min(x, y) = x + y.[Hint: Use a proof by cases, with 20. Prove that given a real number x there exist unique num-
the two cases corresponding to x ≥ y and x< y, respec- bers n and such that x = n + , n is an integer, and
tively.] 0 ≤ < 1.
4. Use a proof by cases to show that min(a, min(b, c)) = 21. Prove that given a real number x there exist unique num-
min(min(a, b), c) whenever a, b, and c are real numbers. bers n and such that x = n − , n is an integer, and
5. Prove using the notion of without loss of generality 0 ≤ < 1.
that min(x, y) = (x + y −|x − y|)/2 and max(x, y) = 22. Use forward reasoning to show that if x is a nonzero real
2
2
(x + y +|x − y|)/2 whenever x and y are real numbers. number, then x + 1/x ≥ 2. [Hint: Start with the in-
2
6. Prove using the notion of without loss of generality that equality (x − 1/x) ≥ 0 which holds for all nonzero real
5x + 5y is an odd integer when x and y are integers of numbers x.]
opposite parity. 23. The harmonic mean of two real numbers x and y equals
7. Prove the triangle inequality, which states that if x and 2xy/(x + y).Bycomputingtheharmonicandgeometric
means of different pairs of positive real numbers, formu-
y are real numbers, then |x|+|y|≥|x + y| (where |x|
represents the absolute value of x, which equals x if x ≥ 0 late a conjecture about their relative sizes and prove your
and equals −x if x< 0). conjecture.
24. The quadratic mean of two real numbers x and y
8. Prove that there is a positive integer that equals the sum
2
2
of the positive integers not exceeding it. Is your proof equals (x + y )/2. By computing the arithmetic and
constructive or nonconstructive? quadratic means of different pairs of positive real num-
bers, formulate a conjecture about their relative sizes and
9. Prove that there are 100 consecutive positive integers that prove your conjecture.
are not perfect squares. Is your proof constructive or non-
∗ 25. Write the numbers 1, 2,..., 2n on a blackboard, where
constructive?
10. Prove that either 2 · 10 500 + 15 or 2 · 10 500 + 16 is not a n is an odd integer. Pick any two of the numbers, j and
k, write |j − k| on the board and erase j and k. Continue
perfect square. Is your proof constructive or nonconstruc- this process until only one integer is written on the board.
tive?
Prove that this integer must be odd.
11. Prove that there exists a pair of consecutive integers such
∗ 26. Suppose that five ones and four zeros are arranged around
that one of these integers is a perfect square and the other
a circle. Between any two equal bits you inserta0and
is a perfect cube.
between any two unequal bits you inserta1to produce
12. Show that the product of two of the numbers 65 1000 − nine new bits. Then you erase the nine original bits. Show
8 2001 + 3 177 ,79 1212 − 9 2399 + 2 2001 , and 24 4493 − that when you iterate this procedure, you can never get
5 8192 + 7 1777 is nonnegative. Is your proof constructive nine zeros. [Hint: Work backward, assuming that you did
or nonconstructive? [Hint: Do not try to evaluate these end up with nine zeros.]
numbers!]
27. Formulate a conjecture about the decimal digits that ap-
13. Prove or disprove that there is a rational number x and an pear as the final decimal digit of the fourth power of an
y
irrational number y such that x is irrational. integer. Prove your conjecture using a proof by cases.
14. Prove or disprove that if a and b are rational numbers, 28. Formulate a conjecture about the final two decimal digits
b
then a is also rational. of the square of an integer. Prove your conjecture using a
15. Show that each of these statements can be used to ex- proof by cases.
2
press the fact that there is a unique element x such that 29. Prove that there is no positive integer n such that n +
3
P(x) is true. [Note that we can also write this statement n = 100.
as ∃!xP(x).] 30. Prove that there are no solutions in integers x and y to the
2
2
a) ∃x∀y(P(y) ↔ x = y) equation 2x + 5y = 14.
b) ∃xP(x) ∧∀x∀y(P(x) ∧ P(y) → x = y) 31. Prove that there are no solutions in positive integers x and
4
4
c) ∃x(P(x) ∧∀y(P(y) → x = y)) y to the equation x + y = 625.
16. Show that if a, b, and c are real numbers and a = 0, then 32. Prove that there are infinitely many solutions in posi-
2
2
2
there is a unique solution of the equation ax + b = c. tive integers x, y, and z to the equation x + y = z .
2
2
2
2
17. Suppose that a and b are odd integers with a = b. Show [Hint: Let x = m − n , y = 2mn, and z = m + n ,
there is a unique integer c such that |a − c|=|b − c|. where m and n are integers.]