數(shù)學(xué)外文翻譯外文文獻(xiàn)英文文獻(xiàn)具體數(shù)學(xué)-預(yù)覽頁
【正文】 是明顯但不正確的，但我們現(xiàn)在可以看看它到底在什么情況下是正確的： J(n) = n=2。這些二進(jìn)制數(shù)一位循環(huán)左移的結(jié)果和一位循環(huán)右移的結(jié)果一樣。讓我們通過引入常量α，β和γ 12 研究這個問題，并嘗試為較一般的遞歸式找到一個閉合形式的公式 f (1) = α。另外，在2的冪的范圍內(nèi)，β的系數(shù)每次減1，直到0。C(n) = l. （7）這里跟以往一樣，n = 2m + l且0 ≤ l 2m，當(dāng)n ≥ 1。A(2n) = 2A(n)；當(dāng) n ≥ 1。我們以一個簡單的f(n)函數(shù)開始，看看是否存在常數(shù)(α, β, γ)可以確定它。3 = 2 2n = 2 當(dāng)α = 1，β = 2且γ = 1的時候，這些等式對于所有的n成立，所以我們不必用數(shù)學(xué)歸納法證明這些參數(shù)滿足f(n) = n。A(n) + C(n) = n.我們的對于(7)式的推測可以通過如下的式子立即解出來：C(n) = n ? A(n) = l以及B(n) = A(n) ? 1 ? C(n) = 2m ? 1 ? l。練習(xí)16和20提供了更多的相關(guān)例子。這樣就會得到 f (bmbm?1...b1b0)2 = (αβbm?1βbm?2 . . . βb1 + βb0)2. （9）好了。 f(dn + j) = cf(n) + βj 當(dāng)0 ≤ j d且n ≥ 1, （10）如同之前的那個，除了我們的起始的數(shù)字的基數(shù)是d，產(chǎn)生值是基數(shù)c。所以，使2變?yōu)?，并假設(shè)0和1變成76和2，代入f(19) = f (201)3 = (576 ?2)10 = 1258,這就是我們的結(jié)果。ve all been investigated repeatedly by mathematicians。 and the case n=2supports the conjecture: J(2) = 1. But a few other small cases dissuade us | the conjecture fails forn=4andn=6.It39。s a good reason for this: The rst trip around the circle eliminates all the even numbers. Furthermore, if nitself 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 let39。 當(dāng)n ≥1:We can now go quickly to largen. For example, we know that J(10) =5, soJ(20) = 2J(10)1 = 2*51 = 9:Similarly J(40) = 17，and we can deduce that J(5*2M)=2M+1 +1But what about the odd case? With2n+1 people, it turns out that person number1is wiped out just after person number 2n, and we39。J(2n) = 2J(n)1。Instead of gettingJ(n)from J(n1), this recurrence is much more effcient,because it reducesnby a factor of2or more each time it39。s left, the solution to our recurrence seems to beJ(2M+L)=2L+1 for m≥0 and 0≤L2M （2）(Notice that if 2M≥n2M+1, the remainder l =n2M satises 0≤L2M+12M=2M.)We must now prove (2). As in the past we use induction, but this timethe induction is on m. When m=0we must havel =0。We might also note that(1) implies the relationJ(2n+1)J(2n)=2Either way, the induction is plete and (2) is established.To illustrate solution (), let39。s 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 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 it39。)We have proved thatJ((bm1bm2...b1b0)2)= (bm1bm2...b1b0m)2。t quite work. For instanceif n=13 we have J(1101)2=(1011)2, but then J(1011)2=(111)2, and the process breaks down。s whose value is 2v(n)1 where v(n) is the number of 1bits in the binary representation ofn. Thus, since v(13) = 3，we have2 or more JJ(J(...J (13)...)) = 23 ? 1 = 7。 2l+ 1 =(2m+l)/2 l =1/3(2m2)If this number l =1/3(2m2) is an integer, then n=2m+lwill be a solution, becauselwill be less than 2m. It39。f (2n) = 2f (n) + β, for n ≥ 1。B(n) = 2m ? 1 ? l。s a better way to proceed, by choosing particular values and then bining them. Let39。Sure enough, it39。 1 + β。 Similarly, we can plug in f(n) =n:1 = α。 n + γ。A(n) ? B(n) ? C(n) = 1。f(2n + j) = 2f(n) + βj, for j = 0, 1and n ≥ 1, （8）if we let β0 = β and β1 = γ。re given the recurrencef(1) = 34f(2) = 5,f(3n) = 10f(n) + 76 for n ≥ 1f(3n + 1) = 10f(n) ? 2 for n ≥ 1f(3n + 2) = 10f(n) + 8, for n ≥ 1and suppose we want to putef(19). Here we have d=3andc=10. Now 19= (201)3and the radixchanging solution tells us to perform a digitbydigit replacement from radix3to radix10. So the leading 2bees a5, and the 0and1bee76and2, givingf(19) = f (201)3 = (576 ?2)10 = 1258,which is our answer.Thus Josephus and the Jewish{Roman war have led us to some interestinggeneral recurrences.,
規(guī)章制度相關(guān)推薦
鄂ICP備17016276號-1