tailieunhanh - concrete mathematics a foundation for computer science phần 9

Đây là cách nó có thể được thực hiện: trung bình của một X biến ngẫu nhiên có giá trị thực trên một không gian xác suất n được định nghĩa lànếu số tiền có khả năng vô hạn này tồn tại. (Ở đây X (n) là viết tắt của các thiết lập của tất cả các giá trị mà X có thể giả định.) | A ANSWERS TO EXERCISES 499 Too easy. A more interesting still unsolved problem Restrict both a and 3 to be 1 and ask when the given multiset determines the unordered pair a Continuing along such lines now leads to the following interpretation Kn is the least number n in the multiset S of all numbers of the form 1 4- a a a2 a 0-2 3 . . . a Ũ2CI3 . . . a where m 0 and each a. is 2 or 3. Thus S 1 3 4 7 9 10 13 15 19 21 22 27 28 31 31 . the number 31 is in S twice because it has two representations 1 2 4 8 16 1 3 9 18. Incidentally Michael F redman 108 has shown that Kn n 1 . that S has no enormous gaps. 3 44 Let dn 1 D Jj mumble q -1 so that oil 1 ql . . dn q - 1 and Now q n and the results follow. This is the solution found by Euler who determined the a s and d s sequentially without realizing that a single sequence would suffice. Let a 1 satisfy a 1 a 2m. Then we find 2Yn a2 a 2 and it follows that The hint follows from since 2ti ti 1 2 n 2 . Let n 0 2 ỵ ĩ1 m and n 0 v 2l 1 y l m where 0 0 9 1. Then mod 1 d where d is 0 or 1. We want to prove that n 2 n I this equality holds if and only if 0 í 9 2-ự2 v 2 l -d 2. To solve the recurrence note that 1 1 and 1 partition the positive integers hence any positive integer a can be written uniquely in the form a where 1 and m are integers with m odd and 0. It follows that a c J. b c is an integer. c c 0. d c is arbitrary. See the answer to exercise in 173 for more general results. Solution by Heinrich Rolletschek. We can replace a 3 by 3 a LPj without changing no . Hence the condition a 3 is necessary. It is also sufficient Let m be the least element of the given multiset and let S be the obtained from the given one by subtracting mn from the nth smallest element for all n. If a consecutive elements of S differ by either or 2 hence the determines According to unpublished notes of William A. it is sufficient to have and 1 linearly independent over the rationals. 500 ANSWERS TO .