3.5 ANSWERS TO EXERCISES 559 29. If 5 = x1×2.. xt is any binary number, we can consider the number v:(n) of times X, Xp-tt+l = x, where 1 5 p 5 n and p is even. Similarly, let y:(n) count the number of times when p is odd. Let v:(n) + v:(n) = v=(n). Now where the V S in these summations have 21c subscripts, 2k -1 of which are asterisks (meaning that they are being summed over-each sum is taken over 22k-1 combinations of zeros and ones), and where ~5 denotes approximate equality (except for an error of at most 2k due to end conditions). Therefore we find that where x = x1 x2k contains r(x) zeros in odd positions and s(x) zeros in even positions. By (2lc)-distribution, the parenthesized quantity tends to k(22k- )/22k = k/2. The re- maining sum is clearly a maximum if y?(n) = u,(n) when T(Z) > s(x), and v:(n) = 0 when r(x) < s(x). So the maximum of the right-hand side becomes O; n n 2n -1 min(r, s) = 2n22n-2 -n au r s ( n > r,s 30. Let f(xl, x2,. , x2k) = sign(xl -x2 +x3 -x4 f. -xzk). Construct a directed graph with 2 nodes labeled (E; x1, . , x2&-1) and (0; xl, , x2&1), where each x is either 0 or 1. Let there be 1 +f(xl, x2,. , xzk) directed arcs from (E; x1, , xZk-1) to (0; x2,. f , x2k), and 1 -f(x1, x2,. . , x2k) directed arcs leading from (0; xl,. , x2&1) to (E; x2,. , x2k). We find that each node has the same number of arcs leading into it as there are leading out; for example, (E; x1,. , x2k-l) has 1 -f(0, x1, , x2k-1) + l-f(l,xl,. ..,52k–1) leading in and l+f(xl,. .,x2k-l,O)+l+f(x1,. . . ,x2k-l,1) leading out, and f(x, xl,. . . , x2&1) = -f(xl, . , x2k-1, x). Drop all nodes that have no paths leading either in or out, i.e., (E; x1,. , xZk-1) if f(0, xl,. . , x2k-1) = +I, or (QXl,.. , XZk-1) if f(l, xl,. . . , x2&1) = -1. The resulting directed graph is seen to be connected, since we can get from any node to (E; 1, 0, 1, 0, ,I) and from this to any desired node. By Theorem 2.3.4.2G, there is a cyclic path traversing each arc; this path has length azk+ , and we may assume that it starts at node (E; 0,. ,O). Construct a cyclic sequence with X1 = … = X2&1 = 0, and Xn+2k-l = x2k if the nth arc of the path is from (E; x1,. , xzk-1) to (0; x2,. , x2k) or from (0; x1,. ,x2&-1) to (E; x2,. . . ,zz~). For example, the graph for k = 2 is shown in Fig. A-5; the arcs of
This entry was posted
on Friday, October 12th, 2007 at 2:23 pm and is filed under MySQL.
You can follow any responses to this entry through the RSS 2.0 feed.
You can leave a response, or trackback from your own site.