Page 130 - Discrete Mathematics and Its Applications

Key Terms and Results 109

33. Adapt the proof in Example 4 in Section 1.7 to prove that checkerboard from 1 to 16, starting in the first row, mov-
if n = abc, where a, b, and c are positive integers, then ing right in this row, then starting in the leftmost square
√ √ √
a ≤ 3 n, b ≤ 3 n,or c ≤ 3 n. in the second row and moving right, and so on. Remove
√
34. Prove that 3 2 is irrational. squares 1 and 16. To begin the proof, note that square 2 is
covered either by a domino laid horizontally, which cov-
35. Prove that between every two rational numbers there is ers squares 2 and 3, or vertically, which covers squares 2
an irrational number.
and 6. Consider each of these cases separately, and work
36. Prove that between every rational number and every irra- through all the subcases that arise.]
tional number there is an irrational number. ∗ 46. Prove that when a white square and a black square are
∗ 37. Let S = x 1 y 1 + x 2 y 2 + ··· + x n y n , where x 1 ,x 2 ,..., removed from an 8 × 8 checkerboard (colored as in the
x n and y 1 ,y 2 ,...,y n are orderings of two different se- text) you can tile the remaining squares of the checker-
quences of positive real numbers, each containing n ele- board using dominoes. [Hint: Show that when one black
ments. and one white square are removed, each part of the parti-
a) Show that S takes its maximum value over all order- tionofthe remainingcellsformedbyinsertingthebarriers
ings of the two sequences when both sequences are shown in the figure can be covered by dominoes.]
sorted (so that the elements in each sequence are in
nondecreasing order).
b) Show that S takes its minimum value over all order-
ings of the two sequences when one sequence is sorted
into nondecreasing order and the other is sorted into
nonincreasing order.
38. Prove or disprove that if you have an 8-gallon jug of wa-
ter and two empty jugs with capacities of 5 gallons and 3
gallons, respectively, then you can measure 4 gallons by
successively pouring some of or all of the water in a jug
into another jug.
39. Verify the 3x + 1 conjecture for these integers.
a) 6 b) 7 c) 17 d) 21
40. Verify the 3x + 1 conjecture for these integers.
47. Show that by removing two white squares and two black
a) 16 b) 11 c) 35 d) 113
squares from an 8 × 8 checkerboard (colored as in the
41. Prove or disprove that you can use dominoes to tile
text) you can make it impossible to tile the remaining
the standard checkerboard with two adjacent corners re- squares using dominoes.
moved (that is, corners that are not opposite).
∗ 48. Find all squares, if they exist, on an 8 × 8 checkerboard
42. Prove or disprove that you can use dominoes to tile a such that the board obtained by removing one of these
standard checkerboard with all four corners removed. square can be tiled using straight triominoes. [Hint: First
43. Prove that you can use dominoes to tile a rectangular use arguments based on coloring and rotations to elimi-
checkerboard with an even number of squares. nate as many squares as possible from consideration.]
44. Prove or disprove that you can use dominoes to tile a ∗ 49. a) Draw each of the five different tetrominoes, where a
5 × 5 checkerboard with three corners removed. tetromino is a polyomino consisting of four squares.
45. Use a proof by exhaustion to show that a tiling using b) For each of the five different tetrominoes, prove or dis-
dominoes of a 4 × 4 checkerboard with opposite corners prove that you can tile a standard checkerboard using
removed does not exist. [Hint: First show that you can these tetrominoes.
assume that the squares in the upper left and lower right ∗ 50. Prove or disprove that you can tile a 10 × 10 checker-
corners are removed. Number the squares of the original board using straight tetrominoes.

Key Terms and Results

TERMS logical operators: operators used to combine propositions
proposition: a statement that is true or false compound proposition: a proposition constructed by combin-
propositional variable: a variable that represents a proposi- ing propositions using logical operators
tion truth table: a table displaying all possible truth values of
truth value: true or false propositions
¬ p (negation of p): the proposition with truth value opposite p ∨ q (disjunction of p and q): the proposition “p or q,” which
to the truth value of p is true if and only if at least one of p and q is true