X web hosting - 564 ANSWERS TO EXERCISES 4.1 node if it
564 ANSWERS TO EXERCISES 4.1 node if it is an initial subsequence of that node. By the infinity lemma this tree has an infinite path (ai, o2, as,. ), and it follows that c,,, ~166 is a limit point of - {YI,YZ,…} in S. By the answer to exercise 16, all numbers of the form (~+bi)/l6~ are representable, when a and b are integers. Therefore if z and y are arbitrary reals and k 2 1, the number sk = (]lS s] + ]16ky]i)/16k is in S + m + ni for some integers m and n. It can be shown that S + m + ni is bounded away from the origin when (m, n) # (0,O). Consequently if 1×1 and ]y] are fixed and k is sufficiently large, we have sk E S, and hk+rn zk = x + yi is in s. [B. Mandelbrot calls S the twindragon, since he noticed that it is essentially obtained by joining two dragon curves belly-to-belly; see his book Fracta1s: Form, Chance, and Dimension (San Francisco: Freeman, 19X ), 313-314. Other properties of the dragon curve are described in C. Davis and D. E. Knuth, J. Recr. Math. 3 (1970), 66-81, 133-149.1 19. If m > u or m < 1, find a E D such that m = a (modulo b); the desired representation will be a representation of m = (m -u)/b followed by a. Note that m > u implies 1 < m < m; m < I implies m < m < U; so the algorithm terminates. [There are no solutions when b = 2. The representation will be unique iff 0 E D; nonunique representation occurs for example when D = (-3, -1,7}, b = 3, since (o)s = (3773~)s. When b 2 3 it is not difficult to show that there are exactly 2b-3 solution sets D in which ]a] < b for all a E D. Furthermore the set D = (0, 1, 2-~b , 3 -E3bn, . . , b - 2 -Eb-2bn, b - 1 -b } gives unique representations, for all b 2 3 and n 2 1, when each ~j is 0 or 1. Reference: Proc. IEEE Symp. Comp. A&h. 4 (1978) l-9.1 20. (a) O.lll... = i.888... = i8.i:: . . . = i8i.i:; . . . = ... = i8:~~~~~.::: has nine representations. (b) A D-fraction .uius . . . always lies between -l/9 and +71/g. Suppose x has ten or more D-decimal representations. Then for sufficiently large k, 10kz has ten representations that differ to the left of the decimal point: 10kx = n1 +fl = . . . = nio + fro where each fj is a D-fraction. By uniqueness of integer representations, the n3 are distinct, say ni < . . . < nls, hence nlo -ni 2 9; but this implies fi -fl0 2 9 > 71/9 -(-l/9), a contradiction. (c) Any number of the form O.uiu2 . , where each uj is -1 or 8, equals i.u;u , . . . where u: = u3 + 9 (and it even has six more representations i8.u; u , . , etc.). 21. We can convert to such a representation by using a method like that suggested in the test for converting to balanced ternary. In contrast to the systems of exercise 20, zero can be represented in infinitely many ways, all obtained from f + c,, 1(-41) . 10wk (or from the negative of this representation) by multiplying it by a power of ten. The representations of unity are 11-4, 4 + 4, 5 -3$-f, 5 - 41-t f, 50-45-333-4, 50-45-441+$, etc., where &a = (&4$)(10-l + 10Y2 + …). [AIUiVf57 (1950) 90-93.1 22. Given some approximation b, . . . blbo with error COckcn bklOk -z > 10Ft for t > 0, we will show how to reduce the error by approximately 10et. (The process can be started by finding a suitable co < k < n bklOk > Z; then a finite number of reductions of this type will make the error less than t.) Simply choose m > n so large that the decimal representation of -lOma has a one in position 10Pt and no ones in positions 10-t+l. 10-t+2. . . 10 . Then 10mcw + fa suitable sum of nowers of 10 between 10 and 1On) + ~o