566 ANSWERS (Linux web host) TO EXERCISES 4.1 either zero or
566 ANSWERS TO EXERCISES 4.1 either zero or one, there is obviously only one way to proceed, otherwise it has a unique reversing representation by induction. [It follows that every positive integer has exactly two such representations with decreasing exponents eo > el > . . . > et: one with t even and the other with t odd.] 28. A proof like that of exercise 27 may be given. Note that a + bi is a multiple of 1 + i by a complex integer if and only if a + b is even. This representation is intimately related to the dragon curve discussed in the answer to exercise 18. 29. It suffices to prove that any collection {TO, 7 1, T2, . . . } satisfying Property B may be obtained by collapsing some collection {SO, S1, S2, . . . }, where SO = (0, 1, . . . , b- 1) and all elements of S1, S2, . . . are multiples of b. To prove the latter statement, we may assume that 1 E TO and that there is a least element b > 1 such that b e TO. We will prove, by induction on n, that if nb @ TO, then nb + 1, nb f 2, . . . , nb + b -1 are not in any of the T3 s; but if nb E TO, then so are nb+ 1, . . . . nb+ b-1. The result then follows with S1 = {nb 1 nb E TO}, 5 2 = TI , & = T2, etc. If nb e TO, then nb = to + tl +. . . , where tl, t2, . . . are multiples of b; hence to < nb is a multiple of b. By induction, (to + k) + tl + t2 + . is the representation of nb + k, for 0 < k < b; hence nb + k @ Tj for any j. If nb E TO and 0 < k < b, let the representation of nb + k be to + tl + … . We cannot have t, = nb + k for j 2 1, lest nb + b have two representations (b -k) + . . . + (nb + k) + . . . = (nb) + . . . + b + . . . By induction, to mod b = k; and the representation nb = (to -k) + tl + . . . implies that to = nb + k. [Reference: AJieuw Archief voor Wiskunde (3) 4 (1956), 15-17. A finite analog of this result was derived by P. A. MacMahon, Combinatory Analysis 1 (1915), 217-223.1 30. (a) Let A3 be the set of numbers n whose representation does not involve b,; then by the uniqueness property, n E Ai iff n + bJ sf A3. Consequently we have n E A3 iff n f 2bj E Aj. It follows that, for j # k, n E Aj n Ak iff n + 2bjbk E A3 f-l Ak. Let m be the number of integers n E A3 n Ak such that 0 < n < 2bjbk. Then this interval contains exactly m integers that are in Aj but not Ak, exactly m in Ak but not Aj, and exactly m in neither Aj nor Ak; hence 4m = 2bjbk. Therefore b, and bk cannot both be odd. But at least one b3 is odd, of course, since odd numbers can be represented. (b) According to (a) we can renumber the b s so that bo is odd and bl, bz, . . are even; then Jbl, ib2, . . . must also be a binary basis, and the process can be iterated. (c) If it is a binary basis, we must have positive and negative dk s for arbitrarily large k, in order to represent f2n when n is large. Conversely, the following algorithm may be used: Sl. [Initialize.] Set k + 0. S2. [Done?] If n = 0, terminate. S3. [Choose.] If n is odd, include 2kdk in the representation, and set n + (n -dk)/2. Otherwise set n +-n/2. S4. [Advance k.] Increase k by 1 and return to S2. 1 At each step the choice is forced; furthermore step S3 always decreases In unless n = -dk, hence the algorithm must terminate. (d) Two iterations of steps S2-S4 in the preceding algorithm will change 4m -+ m, 4m+l+m+5,4m+2-+m+7,4m+3 + m -1. Arguing as in exercise 19, we need only show that the algorithm terminates for -2 5 n 5 8; all other values of n