Discrete Structures, Logic, and Computability, 4th Edition

Chapter 5

Section 5.1

1. a. ⌈n/4⌉. c. ⌊n/4⌋ + 1, which also equals ⌈(n + 1)/4⌉.

2. a. The body of the while loop is entered each time i takes one of the k values 1, 3, 9,. . ., 3^k-1, where 3^k-1 < n ≤ 3^k. Apply log₃ to the inequality to obtain k – 1 < log₃ n ≤ k. So k = ⌈log₃ n⌉.

3. In the following tree, move to the left child of (a, b) whenever a > b.

4. a. n ≤ k^d. b. d = ⌈log_k n⌉.

5. The binary tree must have at least n leaves and a binary tree of depth 5 has at most 32 leaves. So n ≤ 32.

7. a. 7. c. 4.

8. There are 61 possible outcomes. So there must be at least 61 leaves on any tree that solves the problem. If h is the height of a ternary ...