Com web hosting - 45.3 ANALYSIS OF EUCLID S ALGORITHM 363 37. [M38]
45.3 ANALYSIS OF EUCLID S ALGORITHM 363 37. [M38] (T. S. Mote in and E. G. Straus.) Let al, . . . , a, be positive integers. Show that max Qn(a,(l), . . . , sp(n)), over all permutations p(1). . . p(n) of {1,2, . . . , n}, occurs when U,(I) 2 a,(,) 2 a,(2) 2 u~(~–I) 2 .+.; and the minimum occurs when u,cl) 2 a,(n) I U,(3) I %(n-2) I U,(5) 5 *** 5 a,(6) 5 %(n-3) 5 a,(4) < %(n-1) 2 a,(2). 38. [A4~?5] (J. Mikusiriski.) Let K(n) = max,zo T(m, n). Theorem F shows that K(n) < Llog+(&n + 1)j -2; prove that K(n) 2 frlog+(&n + 1)1 - 2. b 39. [A&%] (R. W. Gosper.) If a baseball player s batting average is .334, what is the fewest possible number of times he has been at bat? [Note for non-baseball-fans: Batting average = (number of hits)/(t lmes at bat), rounded to three decimal places.] b 40. [MZB] (The Stern-Peirce tree.) Consider an infinite binary tree in which each node is labeled with the fraction (pl + p,)/(ql + q7), where pl/ql is the label of the node s nearest left ancestor and p7/q7 is the label of the node s nearest right ancestor. (A left ancestor is one that precedes a node in symmetric order, while a right ancestor follows the node. See Section 2.3.1 for the definition of symmetric order.) If the node has no left ancestors, pl/ql = O/l; if it has no right ancestqrs, pr/q7 = l/O. Thus the label of the root is l/l; the labels of its two sqns are l/2 and 2/l; the labels of the four nodes on level 2 are l/3, 213, 312, and 3/l, from left to right; the labels of the eight nodes on level 3 are l/4, 215, 315, 314, 413, 513, 512, 4/l; and so on. Prove that p is relatively prime to q in each label p/q; furthermore, the node labeled p/q precedes the nbde labeled p /q in symmetric order if and only if the labels satisfy p/q < p /q . Find a connection between the cbntinued fraction for the label of a node and the path to that node, thereby showing that each positive rational number appears as the label of exactly one node in the tree. 01 (J. Shallit, 1979.) Show that the regular continued fraction expansion of f+$+$+...=cL 22"-1 VI>1 contains only l s and 2 s and has a fairly Prove that the partial quotients of Liouville s numbers c,, 1 l- gular pattern, when 1 is any integer 2 2. [The latter nurpb&, introduced by J. Liouville in J. de Math. Pures et Appl. 16 (1851), 133-142, were the first explicitly defined numbers to be proved transcendental. The former number and si&lar constants were first proved transcendental by A. J. Kempner, Trans. Amer. Math. Sot. 17 (1916), 476-482.1 42. [M30] (J. Lagrange, 1798.) Let X have the regular continued fraction expansion /AI,-&, . . . /, and let qn = &,(A;, . . . ,An). Let llzll denote the distance from z to the nearest integer, namely min, IZ -p(. Show that IlqXll 2 llqn-lXll for 1 5 q < qn. (Thus the denoniinators qn of the so-call&d convergents pn/q, = /Al,. . . ,An/ are the record-breaking integers that make IlqXll achieve new lows.) 43. [A&?01 (D. W. Matula.) Show that the media@ rounding rule for fixed-slash or floating-slash numbers, Eq. 4.5.1-1, can be implemented simply as follows, when the number z > 0 is not representable: Let the regular continued fraction expansion of 2 be uo + /al, ~2,. . . /, and let pn = Q,+l(uo,. . . ,a,), qn = Qn(ul,. . . , a,). Then round(z) = (pilqi), where (pi/qi) is representable but (pi+l/qi+l) is not. [Hint: See exercise 40 .]