1、Concrete MathematicsR. L. Graham, D. E. Knuth, O. Patashnik?Concrete Mathematics?，1.3 THE JOSEPHUS PROBLEMR. L. Graham, D. E. Knuth, O. PatashnikSixth printing, Printed in the United States of America 1989 by Addison-Wesley Publishing Company，Reference 1-4 pages具體數學R.L.格雷厄姆，D.E.克努特，O.帕塔希尼克?具體數學?，1.3

2、，約瑟夫環問題R.L.格雷厄姆，D.E.克努特，O.帕塔希尼克第一版第六次印刷于美國，韋斯利出版公司，1989年，引用8-16頁遞歸問題本章研究三個樣本問題。這三個樣本問題給出了遞歸問題的感性知識。它們有兩個共同的特點：它們都是數學家們一直反復地研究的問題；它們的解都用了遞歸的概念，按遞歸概念，每個問題的解都依賴于相同問題的假設干較小場合的解。約瑟夫環問題我們最后一個例子是一個以Flavius Josephus命名的古老的問題的變形，他是第一世紀一個著名的歷史學家。據傳說，如果沒有Josephus的數學天賦，他就不可能活下來而成為著名的學者。在猶太|羅馬戰爭中，他是被羅馬人困在一個山洞中的41

3、個猶太叛軍之一，這些叛軍寧死不屈，決定在羅馬人俘虜他們之前自殺，他們站成一個圈，從一開始，依次殺掉編號是三的倍數的人，直到一個人也不剩。但是在這些叛軍中的Josephus和他沒有被揭發的同伴覺得這么做毫無意義，所以他快速的計算出他和他的朋友應該站在這個惡毒的圓圈的哪個位置。在我們的變形了的問題中，我們以n個人開始，從1到n編號圍成一個圈，我們每次消滅第二個人直到只剩下一個人。例如，這里我們以設n= 10做開始。這時的消滅順序是2, 4, 6, 8, 10, 3, 7, 1, 9。所以編號是5的人活下來了。這個問題：就是定位最后活下來的人的數字J(n)。我們剛剛看到的是J(10) = 5的情況。

4、我們可能會推測當n是偶數的時候J(n) =n=2；而且當n= 2的時候結論驗證了假設：J(2) = 1。但是其他一些數字比擬小的情況告訴我們|當n= 4和n= 6的時候這個假設錯誤了。于是我們回到了起點；讓我們試著來個更好的猜測。呃.，J(n)看起來總是奇數。而且事實上，這個現象的原因是：圍成的圓圈的第一輪消滅了所有的編號是偶數的人。之后我們又回到了與我們開始的時候類似的情形，除了人數只有原來一半的人，而且他們的編號改變了。所以，讓我們假設最開始有2n個人，在第一輪結束后，我們剩下而且3將是下一個出局的。這個就像是以n個人開始的情況，除了每個人的編號變為兩倍減一。那就是，J(2n) = 2J(

5、n)-1; 當n 1:我們現在可以快速的計算一下當n比擬大的時候的值。例如，我們知道J(10) = 5，所以J(20) = 2J(10)-1 = 2*5-1 = 9:同樣可知J(40) = 17，進一步我們可以推算出J(5*2M)=2M+1 +1但是，奇數的情況呢？當有2n+ 1個人的時候，編號是1的人會在第2n個人出局后緊接著出局，然后，我們剩下我們再次獲得了形如n個人的情況，但是這次他們的編號是兩倍加一。所以J(2n+ 1) = 2J(n) + 1; 當n 1;與等式J(1) = 1組合，我們得到一個定義了J的所有取值的遞推式:J(1) = 1;J(2n) = 2J(n)-1; 當n 1;

6、 J(2n+ 1) = 2J(n) + 1; 當n 1;這個公式不是從J(n-1)計算J(n)，這個遞歸式更加的“高效，因為他以2為因子使n遞減了一半或更多。我們可以計算J(1;000;000)，如上所示，我們只要應用19次(1)式。但是，我們依舊要尋找一個閉合形式的公式，因為那樣會更加快速和更有意義。總之，這是非常重要的事情。用我們的遞歸式，我們可以很快地建造一張較小取值的表。可能我們可以通過這張表看出模式并猜出結果。瞧！看起來我們可以以2的冪分組(通過表中的豎線)；在每組的開始，J(n)總是1，而且在一組內以2遞增。所以，如果我們把n寫成形如n=2M+J的公式，當2M是不超過n的2的最大次

7、冪，且l是剩余的數。這樣我們的遞歸式的解法看起來是J(2M+L)=2L+1 當m0且0L2M 2(注意如果2Mn2M+1, 那么余下的數l =n-2M 滿足不等式0L0且2M+L=2n那么l是偶數。且通過(1)式和歸納法假設可得J(2M+L)=2J(2M-1+L/2)-1=2(2L/2+1)-1 = 2l+ 1;這個就是我們想要的。奇數的情況證明方法類似，當2M+L=2L+1。我們可能也注意到式子(1)還表達了這樣一個關系J(2n+1)-J(2n)=2總之，這個數學歸納法證明完畢，且(2)式被證明了。為了展示解法(2)式，讓我們來計算一下J(100)。在這個例子中，我們有100 =26+ 36

8、，所以J(100) = 2*36 + 1 = 73現在，我們解決了艱難的局部(解決問題)。我們再說點輕松的：每解決一個問題都可以泛化，使得可以應用一大類問題。當我們已經掌握一項技巧，完整的研究它，看看借助它我們可以走多遠是非常值得的。所以，在這節的余下局部，我們將會研究我們的解法(2)式以及研究遞歸式(1)的一些擴展。這些研究將會展示出所有這樣問題的結構和根底。在我們尋找解法的時候，2的冪起到了重要的作用，所以很自然的，我們想用2的基數表示n和J(n)。假設n的二進制表達式是n=(bmbm-1.b1b0)2;也就是n=bm2m+bm-12m-1+b12+b0每個bi 取值是0或1，且最高位bm

9、 是1. 回想一下n=2M+L我們先后得到如下表達式，n=(1bm-1bm-2.b1b0)2L=(0bm-1bm-2.b1b0)22L=( bm-1bm-2.b1b0)22L+1=(bm-1bm-2.b1b01)2J(n)= (bm-1bm-2.b1b0m)2(最后一個式子是因為J(n) = 2l+ 1以及bm=2L+1以及bm=1。) 我們已經證明J(bm-1bm-2.b1b0)2)= (bm-1bm-2.b1b0m)2; (3)這樣，用計算機編程的專業術語解釋就是我們從n計算J(n)只需要做一位循環左移！多么神奇。例如，如果n= 100 =(1100100)2, 那么J(n) = J(11

10、00100)2=(1001001)2, 也就是64 + 8 + 1 = 73。如果我們從一開始就一直用二進制方法研究，我們可能會立即就發現這個模式。如果我們以n個人開始，迭代J函數m+ 1次，計算機將會作m+ 1次的一位循環左移；所以當n是一個(m+ 1)位的數字，我們可能希望最后又得到n。但是實際上不是。舉個例子，當n= 13， 我們有J(1101)2=(1011)2, 但是之后J(1011)2=(111)2, 這時處理過程中斷了；當0出現在首位的時候會被忽略。事實上，根據定義，J(n)必須總是n, 因為J(n)是存活著的人的編號；所以如果J(n) n我們決不可能通過繼續迭代回溯到n。 重復

11、的應用過程J產生一個遞減的序列值，最終到達一個“固定的值，也就是當J(n) = n的時候。這種循環位移特點使得很容易觀察出來這個固定的值將會是多少：迭代這個方法足夠多的次數，總會產生每個位都是1的模式，其值為 2v(n)-1 , 當v(n)是1-位在整個二進制序列的出現的次數。所以，當v(13) = 3，我們有 2或更多的JJ(J(.J (13).) = 23 1 = 7;同樣的8或更多J(J(.J.) = 210 1 = 1023;很奇怪，但是是正確的。讓我們回到這個問題的最初猜測，也就是當n是偶數的時候J(n) =n=2。一般而言這個結論是明顯但不正確的，但我們現在可以看看它到底在什么情況

12、下是正確的： J(n) = n=2;2l+ 1 =(2m+l)/2l =1/3(2m-2)如果這個式子l =1/3(2m-2) 是一個整數，那么n=2m+l將會是一個解，因為l會小于2m 不難驗證當m是奇數，2m-2是3的倍數，但當m是偶數的時候不成立。(我們將會在第四章研究這個問題。)所以有無窮多個解可以滿足J(n) =n/2，以如下形式開頭：注意這個模式中最右邊的一列。這些二進制數一位循環左移的結果和一位循環右移的結果一樣。(結果都是減半)。好了，我們對函數J了解的全面了；下一步是將這個問題一般化。如果我們的問題得到一個像(1)的遞歸式，但是常數不同，將會發生什么？我們可能就沒有這么幸運能

13、猜到答案了，因為答案可能很復雜。讓我們通過引入常量，和 12 研究這個問題，并嘗試為較一般的遞歸式找到一個閉合形式的公式f (1) = ;f (2n) = 2f (n) + , 當 n 1;4f (2n + 1) = 2f (n) + , 當 n 1.(我們開始的遞歸式中 = 1， = 1，且 = 1。)以f (1) = 開始計算，我們可以構建出來接下來的廣義形式遞歸式的對n取值較小的表： 可以看出來的系數是小于n的最大的2的冪。另外，在2的冪的范圍內，的系數每次減1，直到0。而的系數那么從0開始每次增加1。所以，我們的表達式f(n)的形式是f(n) = A(n) + B(n) + C(n),

14、 6通過與之相關的，和別離，可得A(n) = 2m;B(n) = 2m 1 l;C(n) = l.7這里跟以往一樣，n = 2m + l且0 l 2m，當n 1。使用數學歸納法證明(6)式和(7)式并不是一件非常艱難的事情，但是這個計算過程是繁雜而且沒有技術含量的。而且現在有個更好的方法來計算，通過帶入選定具體的值，然后比照計算他們。13讓我們通過具體的例子 = 1， = = 0來說明這個方法，當假設f(n)等于A(n)：遞歸式(4)變為A(1) = 1;A(2n) = 2A(n)；當 n 1;A(2n + 1) = 2A(n)；當 n 1;可以肯定的是,A(2m + l) = 2m是正確的(

15、通過對m進行數學歸納法可以證明)。接下來，我們將反用遞歸式(4)以及解法(6)式。我們以一個簡單的f(n)函數開始，看看是否存在常數(, , )可以確定它。將常函數f(n) = 1帶入遞歸式(4)可得1 = ;2 = 2 1 + ;3 = 2 1 + ;所以取值(, , ) = (1, 1, 1)滿足這些等式，且有A(n) B(n) C(n) =f(n) = 1。同樣我們可以帶入f(n) = n：1 = ;2n = 2 n + ;2n + 1 = 2 n + ;當 = 1， = 2且 = 1的時候，這些等式對于所有的n成立，所以我們不必用數學歸納法證明這些參數滿足f(n) = n。我們已經知道

16、f(n) = n在這個例子中是解，因為遞歸式(4)為每個n的取值唯一的定義了f(n)。現在我們已經完成了核心的局部！我們已經表示了(6)式的函數A(n)，B(n)以及C(n)，他們解決了廣義的(4)式，滿足公式A(n) = 2m,當 n = 2m + l且0 l 2m;A(n) B(n) C(n) = 1;A(n) + C(n) = n.我們的對于(7)式的推測可以通過如下的式子立即解出來：C(n) = n A(n) = l以及B(n) = A(n) 1 C(n) = 2m 1 l。這個過程已經接近于展示一個驚奇、有用的repertoire method來解決遞歸式問題。首先，我們要尋找我們的

17、解法中的通用參數；這給予了我們能解得各個局部的特例。我們需要跟獨立的參數數量(在這個例子中是三個，和)同樣多的獨立的特解。練習16和20提供了更多的相關例子。我們知道原來的遞歸式J有一個神奇的解法，也就是二進制：J (bmbm1.b1b0)2 = (bm1.b1b0bm)2, 當 bm = 1.那么，廣義的Josephus遞歸式也能如此神奇么？當然，為什么不呢？我們可以把這個廣義的遞歸式(4)重寫成如下形式f(1) = ;f(2n + j) = 2f(n) + j, 當 j = 0, 1且n 8假設我們設0 = 且1 = 。這個遞歸式的展開式，二進制表示如下：f (bmbm1.b1b0)2 =

18、 2f (bmbm1.b1)2 + b0 = 4f (bmbm1.b2)2 + 2b1 + b1 = 2mf (bm)2 + 2m1bm1 + . . + b0 = 2m + 2m1bm1 + . . .+ b0.假設我們現在不管162的基數標記，隨便讓數字取代二進制中的0和1。這樣就會得到 f (bmbm1.b1b0)2 = (bm1bm2 . . . b1 + b0)2. 9好了。如果我們把(5)式換一種寫法17，我們會更早些看到這個模式：舉個例子，當n = 100 = (1100100)2的時候，我們原來的Josephus取值為 = 1， = 1，且 = 1帶入后構造結論跟之前一樣。這個

19、循環左移的特點之所以能滿足是因為每個二進制數據塊(10.000)2在表示n的時候的時候轉化為(1 1. 1 1)2 = (0 0 . 0 1)2.所以我們改變曾給出的對遞歸式(8)的精簡的解法(9)式。如果我們已經不受約束了，我們就可以使它更加一般化18，所以遞歸式f(j) = aj,當1 j d;f(dn + j) = cf(n) + j 當0 j d且n 1, 10如同之前的那個，除了我們的起始的數字的基數是d，產生值是基數c。所以，這個基數改變了的解法是f (bmbm1.b1b0)d = (bmbm1bm2 . . . b1b0)c. 11例如，假設一個幸運的巧合19下我們獲得了一個遞歸

20、式f(1) = 34f(2) = 5,f(3n) = 10f(n) + 76 當n 1f(3n + 1) = 10f(n) 2 當n 1f(3n + 2) = 10f(n) + 8, 當n 1假設我們想計算f(19)。這里我們有d = 3和c = 10。現在19 = (201)3，通過這個基數改變了的解法，我們把數字一位一位的替換，把每個數字從基于基數3的表示方法替換為基數是10的。所以，使2變為5，并假設0和1變成76和-2，代入f(19) = f (201)3 = (576 2)10 = 1258,這就是我們的結果。所以Josephus以及猶太羅馬戰爭留給我們一些有趣的廣義遞歸式。1. R

21、ecurrent ProblemsTHIS CHAPTER EXPLORES three sample problems that give a feel forwhats to come. They have two traits in common: Theyve all been investi-gated repeatedly by mathematicians; and their solutions all use the idea ofrecurrence, in which the solution to each problem depends on the solution

22、sto smaller instances of the same problem.1.3 THE JOSEPHUS PROBLEMIn our Our nal introductory example is a variant of an ancient problem named for Flavius Josephus, a variation, we start withnpeople numbered 1 tonaround a circle, and we eliminate everysecondremaining person until only one survives.

23、For example, heres the starting conguration forn=10:The elimination order is2, 4, 6, 8, 10, 3, 7, 1, 9, so 5survives. The problem:Determine the survivors number,J(n).We just saw thatJ(10) =5. We might conjecture that J(n) =n=2when nis even; and the case n=2supports the conjecture: J(2) = 1. But a fe

24、w other small cases dissuade us | the conjecture fails forn=4andn=6.Its back to the drawing board; lets try to make a better guess. Hmmm : : :J(n)always seems to be odd. And in fact, theres a good reason for this: The rst trip around the circle eliminates all the even numbers. Furthermore, if nitsel

25、f is an even number, we arrive at a situation similar to what we began with, except that there are only half as many people, and their numbers have changed.So lets suppose that we have2npeople originally. After the rst go-round, were left withnd3will be the next to go. This is just like starting out

26、 withnpeople, except that each persons number has been doubled and decreased by1. That is,J(2n) = 2J(n)-1; 當n 1:We can now go quickly to largen. For example, we know that J(10) =5, soJ(20) = 2J(10)-1 = 2*5-1 = 9:Similarly J(40) = 17，and we can deduce that J(5*2M)=2M+1 +1But what about the odd case?

27、With2n+1 people, it turns out that person number1is wiped out just after person number 2n, and were left with Again we almost have the original situation withnpeople, but this time their numbers are doubled andincreased by1. ThusJ(2n+ 1) = 2J(n) + 1; for n 1;Combining these equations with J(1) = 1 g

28、ives us a recurrence that denes J in all cases:J(1) = 1;J(2n) = 2J(n)-1; for n 1; J(2n+ 1) = 2J(n) + 1; for n 1;Instead of gettingJ(n)from J(n-1), this recurrence is much more effcient,because it reducesnby a factor of2or more each time its applied. We could computeJ(1000000), say, with only 19 appl

29、ications of (1.8). But still, we seek a closed form, because that will be even quicker and more informative. After all, this is a matter of life or death.Our recurrence makes it possible to build a table of small values very quickly. Perhaps well be able to spot a pattern and guess the answer.Voila!

30、 It seems we can group by powers of 2 (marked by vertical lines in the table);J(n) is always 1at the beginning of a group and it increases by2 within a group. So if we writenin the form n=2M+J, where 2M is the largest power of 2not exceedingnand wherel is whats left, the solution to our recurrence s

31、eems to beJ(2M+L)=2L+1 for m0 and 0L2M 2(Notice that if 2Mn2M+1, the remainder l =n-2M satises 0L0and2M+L=2n , then l is even andJ(2M+L)=2J(2M-1+L/2)-1=2(2L/2+1)-1 = 2l+ 1;by (1) and the induction hypothesis; this is exactly what we want. A similar proof works in the odd case, when 2M+L=2L+1。We migh

32、t also note that(1) implies the relationJ(2n+1)-J(2n)=2Either way, the induction is complete and (2) is established.To illustrate solution (1.9), lets compute J(100). In this case we have100 =26+ 36, so J(100) = 2*36 + 1 = 73Now that weve done the hard stuff (solved the problem) we seek thesoft: Eve

33、ry solution to a problem can be generalized so that it applies to a wider class of problems. Once weve learned a technique, its instructive to look at it closely and see how far we can go with it. Hence, for the rest of this section, we will examine the solution (2) and explore some generalizations

34、of the recurrence (1). These explorations will uncover the structure that underlies all such problemsPowers of 2 played an important role in our finding the solution, so itsnatural to look at the radix2 representations of nandJ(n). Suppose nsbinary expansion isn=(bmbm-1.b1b0)2;that is,n=bm2m+bm-12m-

35、1+b12+b0where each bi is either 0or1and where the leading bit bm is 1. Recalling that n=2M+L, we have, successively, n=(1bm-1bm-2.b1b0)2L=(0bm-1bm-2.b1b0)22L=( bm-1bm-2.b1b0)22L+1=(bm-1bm-2.b1b01)2J(n)= (bm-1bm-2.b1b0m)2(The last step follows because J(n) = 2l+ 1 and because bm=2L+1 and bm=1。)We hav

36、e proved thatJ(bm-1bm-2.b1b0)2)= (bm-1bm-2.b1b0m)2; (3)that is, in the lingo of computer programming, we get J(n) from nby doing a one-bit cyclic shift left! Magic. For example, if n= 100 =(1100100)2 then J(n) = J(1100100)2=(1001001)2, which is 64+8+1=73. If we had been working all along in binary n

37、otation, we probably would have spotted this pattern immediately.if we start with nand iterate theJ function m+1 times, were doing m+1 one-bit cyclic shifts; so, sincenis an (m+1)-bit number, we might expect to end up with nagain. But this doesnt quite work. For instanceif n=13 we have J(1101)2=(101

38、1)2, but then J(1011)2=(111)2, and the process breaks down; the 0disappears when it becomes the leading bit.In fact, J(n) must always be n, by denition, sinceJ(n) is the survivors number; hence if J(n) nwe can never get back up tonby continuing to iterate.Repeated application ofJproduces a sequence

39、of decreasing values that eventually reach a fixed point, where J(n) = n The cyclic shift property makes it easy to see what that fixed point will be: Iterating the function enough times will always produce a pattern of all1s whose value is 2v(n)-1 where v(n) is the number of 1bits in the binary rep

40、resentation ofn. Thus, since v(13) = 3，we have2 or more JJ(J(.J (13).) = 23 1 = 7;Similarly8or moreJ(J(.J.) = 210 1 = 1023;Curious, but trueLets return briefly to our rst guess, thatJ(n) =n/2whennis even. This is obviously not true in general, but we can now determine exactly when it is true:J(n) =

41、n=2;2l+ 1 =(2m+l)/2l =1/3(2m-2)If this number l =1/3(2m-2) is an integer, then n=2m+lwill be a solution, becauselwill be less than 2m. Its not hard to verify that 2m-2 is a multiple of3whenmis odd, but not when mis even. (We will study such things in Chapter 4.) Therefore there are innitely many sol

42、utions to the equationJ(n) =n/2 beginning as follows:Notice the pattern in the rightmost column. These are the binary numbers for which cyclic-shifting one place left produces the same result as ordinary-shifting one place right (halving).OK, we understand theJfunction pretty well; the next step is

43、to general-ize it. What would have happened if our problem had produced a recurrence that was something like (1), but with diferent constants? Then we might not have been lucky enough to guess the solution, because the solution might have been really weird. Lets investigate this by introducing const

44、ants ， and and trying to nd a closed form for the more general recurrencef (1) = ;f (2n) = 2f (n) + , for n 1;4f (2n + 1) = 2f (n) + , for n 1.(Our original recurrence had = 1， = 1 and = 1。) Starting with f (1) = and working our way up, we can construct the following general table for small values o

45、f n:It seems that s coecient is ns largest power of 2. Furthermore, between powers of2, s coecient decreases by 1down to0 and s increases by 1 up from0. Therefore if we express f(n) in the formf(n) = A(n) + B(n) + C(n), 6by separating out its dependence on ， and , it seems thatA(n) = 2m;B(n) = 2m 1

46、l;C(n) = l.7Here, as usual, n = 2m + l and 0 l 2m，for n 1。Its not terribly hard to prove (1.13) and (1.14) by induction, but the calculations are messy and uninformative. Fortunately theres a better way to proceed, by choosing particular values and then combining them. Lets illustrate this by consid

47、ering the special case = 1， = = 0 when f(n) is supposed to be equal toA(n): Recurrence (1.11) becomesA(1) = 1;A(2n) = 2A(n)；for n 1;A(2n + 1) = 2A(n)；for n 1;Sure enough, its true (by induction onm) that ,A(2m + l) = 2mNext, lets use recurrence (1.11) and solution (1.13)in reverse, by starting with

48、a simple function f(n)and seeing if there are any constants(, , ) that will dene it. Plugging the constant functionf(n) =1into (1.11) says that A neat idea!1 = ;2 = 2 1 + ;3 = 2 1 + ;hence the values(, , ) = (1, 1, 1) satisfying these equations will yield A(n) B(n) C(n) =f(n) = 1。 Similarly, we can

49、plug in f(n) =n:1 = ;2n = 2 n + ;2n + 1 = 2 n + ;These equations hold for allnwhen = 1， = 2 and = 1, so we dontneed to prove by induction that these parameters will yieldf(n) = n. Wealreadyknow thatf(n) =nwill be the solution in such a case, because therecurrence (1.11) uniquely denesf(n) for every

50、value of n.And now were essentially done! We have shown that the functionsA(n),B(n), and C(n) of (1.13), which solve (1.11) in general, satisfy the equationsA(n) = 2m,or n = 2m + l and 0 l 2m;A(n) B(n) C(n) = 1;A(n) + C(n) = n.Our conjectures in (1.14) follow immediately, since we can solve these eq

51、uations to get C(n) = n A(n) = l and B(n) = A(n) 1 C(n) = 2m 1 l。This approach illustrates a surprisingly usefulrepertoire methodfor solv-ing recurrences. First we nd settings of general parameters for which we know the solution; this gives us a repertoire of special cases that we can solve.Then we

52、obtain the general case by combining the special cases. We need as many independent special solutions as there are independent parameters (in this case three, for ， and ) Exercises 16 and 20 provide further examples of the repertoire approach.We know that the originalJ-recurrence has a magical solution, in binary: J (bmbm1.b1b0)2 = (bm1.b1b0bm)2, when bm = 1.Does the generalized Josephus recurrence admit of such magic?Sure, why not? We can rewrite the generalized recurrenc