TAOCP 5.4.2 Exercise 13
Working
Section 5.4.2: The Polyphase Merge
Exercise 13. [22] [22] Prove the following rather odd property of perfect Fibonacci distributions: When the final output will be on tape number 7, the number of runs on each other tape is odd; when the final output will be on some tape other than 7, the number of runs will be odd on that tape, and it will be even on the others. [See (1).]
14, [M35] Let T,(x) = 0,59 Tnev*, where T;,(x) is the polynomial defined in (16). a) Show that for each k there is a number n(k) such that Tin < Tar <+-- < Trek > Tin(k)t+yk 207°: b) Given that Typ: < Tyg and n’ <n, prove that Tr, < Tnx for all k > k’. c) Prove that there is a nondecreasing sequence (M,,) such that ©,(S) = min;>12;(S) when Mn < S < Mn41, but Y,(S) > minj>1 Yj (S) when S > Mn41. [See (19).]
Verified: no
Solve time: 4m09s
Working