Web site templates - 4.6.3 ANSWERS TO EXERCISES 635 10. By using
4.6.3 ANSWERS TO EXERCISES 635 10. By using the FATHER representation discussed in Section 2.3.3: Make use of a table f[j], 1 5 j < 100, such that f[l] = 0 and f[j] is the number of the node just above j for j 2 2. (The fact that each node of this tree has degree at most two has no effect on the efficiency of this representation; it just makes the tree look prettier as an illustration.) 11. 1, 2, 3, 5, 10, 20, (23 or 40), 43; 1, 2, 4, 8, 9, 17, (26 or 34), 43; 1, 2, 4, 8, 9, 17, 34, (43 or 68), 77; 1, 2, 4, 5, 9, 18, 36, (41 or 72), 77. If either of the latter two paths were in the tree we would have no possibility for n = 43, since the tree must contain either 1, 2, 3, 5 or 1, 2, 4, 8, 9. 12. No such infinite tree can exist, since I(n) # 2*(n) for some n. 13. For Case 1, use a Type-l chain followed by ZAfC + 2B+C + 2A $ 2B; or use the factor method. For Case 2, use a Type-2 chain followed by 2AfC+1 + 2BfC + 2A + 2B. For Case 3, use a Type-5 chain followed by addition of 2A + 2A-1, or use the factor method. For Case 4, n = 135.2O, so we may use the factor method. 14. (a) It is easy to verify that steps r -1 and r -2 are not both small, so let us assume that step r-l is small and step r-2 is not. If c = 1, then x(a,-1) = X(a,-.k), so Ic = 2; and since 4 < ~(a,) = v(a?-l) + ~(a~-k) -1 5 ~(a,-1) + 1, we have ~(a,-~) 2 3, making T - 1 a star step (lest as, al, . . , ~~~-3, uTPl include only one small step). Then ~~-1 = u7-z + a +-4 for some q, and if we replace ~~-2, a,-~, a7 by a7--2, 2u7--2, 2a,-2 + ur-q = u7, we obtain another counterexample chain in which step r is small; but this is impossible. On the other hand, if c 2 2, then 4 5 ~(a,) 2 ~(a,-I) + v(u7-k) -2 5 ~(a,-I); hence v(u~-1) = 4, ~(a,+) = 2, and c = 2. This leads readily to an impossible situation by a consideration of the six types in the proof of Theorem B. (b) If X(u,-k) < m -1, we have c 2 3, so v(u?-k) + ~(a,-1) 2 7 by (22); therefore both v(u~-~) and ~(a,-1) are 2 3. AI1 small steps must be < r -k, and x(u,-,) = m -Ic + 1. If k 2 4, we must have c = 4, k = 4, v(u7.-r) = v(G-~) = 4; thus u,-~ 2 2m+2m-1+2m-2, and ~~-1 must equal 2 +2m- +2m-2+2 -3; but a7--4 2 $a,-1 now implies that ~~-1 = 8~~~4. Thus k = 3 and ~~~-1 > 2 +2 -l. Since u7–2 < 2 and ~~-3 < 2m-1, step r -1 must be a doubling; but step r -2 is a nondoubling, since u7-r # 4ur-s. Furthermore, since v(ur-s) 2 3, r -3 is a star step; and ur-2 = ur-s + a?-5 would imply that us-s = 27n-2, hence we must have aT-s = u7–3 + ~~~-4. As in a similar case treated in the text, the only possibility is now seen to be u7–4 = 2m-2 + 2m-3, ur–3 = 2m-2 + 2m-3 + 2df1 + 2d, ~~-1 = 2m + p–l+ 2d+2 + 2d+l, and even this possibility is impossible. 16. lB(n) = l(n) j- v(n) -1; so if n = 2k, I (n)/x(n) = 1, but if n = 2k+1 -1, l (n)/A(n) = 2. 17. Let ii < . < it. Delete any intervals I,+ that can be removed without affecting the union I1 U IJ It. (The interval (jk, ik] may be dropped out if either jk+l 5 jk or jl < j2 < . . . and jk+i 2 ik-1.) Now combine overlapping intervals (jl, ill, . , (j,, id] into an interval (j , i ] = (ji, id] and note that a,, < a,,(1 + 6)21-J1+ +zd-jd 5 u,,(l + 6)2@ + ), since each point of (j , i ] is covered at most twice in (j,, ii] u . . . u (jd, id].