1.3 THE JOSEPHUS PROBLEM 11 But there's a sim- (1.9)reduces to J(1)=1,which is true.The induction step has two parts, pler way!The depending on whether L is even or odd.If m >0 and 2m+L=2n,then L is key fact is that J(2m）=1for even and all m,and this follows immedi- J2m+)=2J2m-1+/2)-1=2(2/2+1)-1=21+1, ately from our first equation, by (1.8)and the induction hypothesis;this is exactly what we want.A similar J2n)=2Jn)-1. proof works in the odd case,when 2"+l=2n 1.We might also note that Hence we know that (1.8)implies the relation the first person will survive whenever J(2n+1)-2n)-2. n isapowerof2. And in the gen- Either way,the induction is complete and (1.9)is established. eral case,when n=2m+1, To illustrate solution (1.9),let's compute J(100).In this case we have the number of 100=26+36,s0J(100)=2.36+1=73. people is reduced Now that we've done the hard stuff (solved the problem)we seek the to a power of 2 soft:Every solution to a problem can be generalized so that it applies to a after there have been executions. wider class of problems.Once we've learned a technique,it's instructive to The first remaining look at it closely and see how far we can go with it.Hence,for the rest of this person at this point, section,we will examine the solution (1.9)and explore some generalizations the survivor,is number 21+1. of the recurrence (1.8).These explorations will uncover the structure that underlies all such problems. Powers of 2 played an important role in our finding the solution,so it's natural to look at the radix 2 representations of n and J(n).Suppose n's binary expansion is n=(bm bm-1..b1bo)2; that is, n=bm2m+bm-12m-1+…+b12+b0, where each bi is either 0 or 1 and where the leading bit bm is 1.Recalling that n=2"+L,we have,successively, n (16m-16m-2...b1 6o)2, L=(0bm-1bm-2…b1bo2, 21=(bm-1bm-2.b1bo0j2, 21+1=(bm-1bm-2.b1b01)2, J(n)=(bm-1bm-2...b1 bo bm)2. (The last step follows because J(n)=21+1 and because bm=1.)We have proved that ((bm bm-1...b1 bo)2)=(bm-1...bi bo bm)2; (1.10)
But there’s a simpler way! The key fact is that J(2”) = 1 for all m, and this follows immediately from our first equation, J(2n) = 2J(n)-1. Hence we know that the first person will survive whenever n isapowerof2. And in the general case, when n = 2”+1, the number of people is reduced to a power of 2 after there have been 1 executions. The first remaining person at this point, the survivor, is number 21+ 1 . 1.3 THE JOSEPHUS PROBLEM 11 (1.9) reduces to J(1) = 1, which is true. The induction step has two parts, depending on whether 1 is even or odd. If m > 0 and 2”’ + 1= 2n, then 1 is even and J(2” + 1) = 2J(2”-’ + l/2) - 1 = 2(21/2 + 1) - 1 = 21f 1 , by (1.8) and the induction hypothesis; this is exactly what we want. A similar proof works in the odd case, when 2” + 1= 2n + 1. We might also note that (1.8) implies the relation J(2nf 1) - J(2n) = 2. Either way, the induction is complete and (1.9) is established. To illustrate solution (l.g), let’s compute J( 100). In this case we have 100 = 26 + 36, so J(100) = 2.36 + 1 = 73. Now that we’ve done the hard stuff (solved the problem) we seek the soft: Every solution to a problem can be generalized so that it applies to a wider class of problems. Once we’ve learned a technique, it’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 (1.9) and explore some generalizations of the recurrence (1.8). These explorations will uncover the structure that underlies all such problems. Powers of 2 played an important role in our finding the solution, so it’s natural to look at the radix 2 representations of n and J(n). Suppose n’s binary expansion is n = (b, b,-l . . bl bo)z ; that is, n = b,2” + bmP12mP’ + ... + b12 + bo, where each bi is either 0 or 1 and where the leading bit b, is 1. Recalling that n = 2” + 1, we have, successively, n = (lbm~lbm~.2...blbo)2, 1 = (0 b,pl b,p2.. . bl b0)2 , 21 = (b,p, bmp2.. . b, b. 0)2, 21+ 1 = (b,p, bmp2.. . bl b. 1 )2 , J(n) = (bm-1 brn-2.. .bl bo brn)z. (The last step follows because J(n) = 2l.+ 1 and because b, = 1.) We have proved that J((bmbm--l ...bl b0)2) = (brn-1 ...bl bobml2; (1.10)
12 RECURRENT PROBLEMS that is,in the lingo of computer programming,we get J(n)from n by doing a one-bit cyclic shift left!Magic.For example,if n =100=(1 100100)2 then Jm=J(1100100)z）=(1001001)2,which is64+8+1=73.If we had been working all along in binary notation,we probably would have spotted this pattern immediately. If we start with n and iterate the J function m +1 times,we're doing (“Iteration”ais m+1 one-bit cyclic shifts;so,since n is an (m+1 )-bit number,we might applying a function expect to end up with n again.But this doesn't quite work.For instance to itself.) if n 13 we have J((1101)2)=(1011)2,but then J((1011)2)=(111)2 and the process breaks down;the 0 disappears when it becomes the leading bit. In fact,J(n)must always be n by definition,since J(n)is the survivor's number;hence if J(n)<n we can never get back up to n by continuing to iterate. Repeated application of J produces a sequence 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 all I's whose value is 2v(1, where v(n)is the number of 1 bits in the binary representation of n.Thus, since v(13)=3,we have 2 or more I's JU(..(13)..)=23-1=7: similarly Curiously enough, if M is a compact 8or more C n-manifold (n 1),there ..j0(101101101101011)2)..)=210~1=1023. exists a differen- tiable immersion of Curious,but true M into R2n-vimi but not necessarily Let's return briefly to our first guess,that J(n)=n/2 when n is even. into R2n vin)-1 This is obviously not true in general,but we can now determine exactly when I wonder if Jose- it is true: phus was secretly a topologist? J(n)=n/2, 2L+1=(2m+)/2, 1=(2m-2). If this numberI=(22)is an integer,then n=2"+I will be a solution, because l will be less than 2m.It's not hard to verify that 2m-2 is a multiple of 3 when m is odd,but not when m is even.(We will study such things in Chapter 4.)Therefore there are infinitely many solutions to the equation
12 RECURRENT PROBLEMS that is, in the lingo of computer programming, we get J(n) from n by doing a one-bit cyclic shift left! Magic. For example, if n = 100 = (1 lOOlOO) then J(n) = J((1100100)~) = (1001001) 2, which is 64 + 8 + 1 = 73. If we had been working all along in binary notation, we probably would have spotted this pattern immediately. If we start with n and iterate the J function m + 1 times, we’re doing (“iteration” means m + 1 one-bit cyclic shifts; so, since n is an (mfl )-bit number, we might applying a function expect to end up with n again. But this doesn’t quite work. For instance to itself.) if n = 13 we have J((1101)~) = (1011)2, but then J((1011)~) = (111)~ and the process breaks down; the 0 disappears when it becomes the leading bit. In fact, J(n) must always be < n by definition, since J(n) is the survivor’s number; hence if J(n) < n we can never get back up to n by continuing to iterate. Repeated application of J produces a sequence 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 all l's whose value is 2”(“) - 1, where y(n) is the number of 1 bits in the binary representation of n. Thus, since Y( 13) = 3, we have 2 or more I’s j(r(.TTi(l3,...)) = 23-l = 7; similarly 8 or more ~((101101101101011)2)...)) = 2" - 1 = 1023. Curiously enough, if M is a compact C” n-manifold (n > 1), there exists a differenCable immersion of Luria r*mm~ ’ -IUS, but true. M intO R*” ~Ytnl Let’s return briefly to our first guess, that J(n) = n/2 when n is even. but not necessarily into ~2” vinl-1, This is obviously not true in general, but we can now determine exactly when 1 wonder if Joseit is true: phus was secretly a topologist? J(n) = n/2, 21+ 1 = (2"+1)/2, 1 = f(2” -2). If this number 1 = i (2”’ - 2) is an integer, then n = 2” + 1 will be a solution, because 1 will be less than 2m. It’s not hard to verify that 2m -2 is a multiple of 3 when m is odd, but not when m is even. (We will study such things in Chapter 4.) Therefore there are infinitely many solutions to the equation
1.3 THE JOSEPHUS PROBLEM 13 J(n)=n/2,beginning as follows: m L n=2m+1 J(n)=2L+1=n/2 n (binary) 1 0 2 1 10 3 2 10 5 1010 5 10 42 21 101010 7 42 170 85 10101010 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 the J function pretty well;the next step is to general- ize it.What would have happened if our problem had produced a recurrence that was something like (1.8),but with different constants?Then we might not have been lucky enough to guess the solution,because the solution might have been really weird.Let's investigate'this by introducing constants &B, Looks like Greek and y and trying to find a closed form for the more general recurrence to me. f(1)=X; f(2n)=2f(n)+B, forn≥l (1.11) f2n+1)=2fn)+Y, forn≥1. (Our original recurrence had a =1,B=-1,and Y=1.)Starting with f(1)=a and working our way up,we can construct the following general table for small values of n: n f(n) 1 a 2 2x+B +Y 4 40+36 (1.12) 5 4x+28+Y 6 4x+B+2y 7 4a +3y 8 8+7β 98x+6+Y It seems that a's coefficient is n's largest power of 2.Furthermore,between powers of 2,B's coefficient decreases by 1 down to 0 and y's increases by 1 up from 0.Therefore if we express f(n)in the form f(n)=A(n)a B(n)B+C(n)Y, (1.13)
1.3 THE JOSEPHUS PROBLEM 13 J(n) = n/2, beginning as follows: m 1 n=2m+l J(n) = 21f 1 = n/2 n (binary) 1 0 2 1 1 0 3 2 1 0 5 1010 5 1 0 42 21 101010 7 42 170 85 10101010 Notice the pattern in the rightmost column. These are the binary numbers for which cyclic-shifting one place left produces the same result as ordinaryshifting one place right (halving). Looks like Greek to me. OK, we understand the J function pretty well; the next step is to generalize it. What would have happened if our problem had produced a recurrence that was something like (1.8), but with different constants? Then we might not have been lucky enough to guess the solution, because the solution might have been really weird. Let’s investigate’this by introducing constants a, 6, and y and trying to find a closed form for the more general recurrence f(1) = cc; f(2n) = 2f(n) + fi, for n 3 1; (1.11) f(2n+1)=2f(n)+y, for n 3 1. (Our original recurrence had a = 1, fi = -1, and y = 1.) Starting with f (1) = a and working our way up, we can construct the following general table for small values of n: n f(n) l a 2 2a-f 6 3201 +y 4 4af3f3 5 4a+28+ y 6 4a+ fi+2y 7 4a + 3Y 8 8a+7p 9 8a+ 6fl + y (1.12) It seems that a’s coefficient is n’s largest power of 2. Furthermore, between powers of 2, 0’s coefficient decreases by 1 down to 0 and y’s increases by 1 up from 0. Therefore if we express f(n) in the form f(n) = A(n) a + B(n) B + C(n)y , (1.13)
14 RECURRENT PROBLEMS by separating out its dependence on a,B,and y,it seems that A(n)=2m; B(n)=2m-1-1; (1.14） C(n)=L. Here,as usual,n=2m+land0≤L<2m,forn≥l. It's not terribly hard to prove (1.13)and (1.14)by induction,but the Ho/d onto your calculations are messy and uninformative.Fortunately there's a better way hats,this next part to proceed,by choosing particular values and then combining them.Let's is new stuff. illustrate this by considering the special case a=1,B=y=0,when f(n)is supposed to be equal to A(n):Recurrence (1.11)becomes A(1)=1; A(2n)=2A(n),forn≥1； A(2n +1)=2A(n),for n>1. Sure enough,it's true (by induction on m)that A(2m+)=2m Next,let's use recurrence (1.11)and solution (1.13)in reverse,by start- ing with a simple function f(n)and seeing if there are any constants(,B,Y) that will define it.Plugging in the constant function f(n)=I says that A neat idea! 1=a; 1=2.1+β； 1=2.1+Y; hence the values(a,B,y)=(1,-1,-1)satisfying these equations will yield A(n)B(n)C(n)=f(n)=1.Similarly,we can plug in f(n)=n: 1=0 2n=2n+B; 2m+1=2.n+Yi These equations hold for all n when a =1,B=0,and y=1,so we don't need to prove by induction that these parameters will yield f(n)=n.We already know that f(n)=n will be the solution in such a case,because the recurrence (1.11)uniquely defines f(n)for every value of n. And now we're essentially done!We have shown that the functions A(n), B(n),and C(n)of (1.13),which solve (1.11)in general,satisfy the equations A(n)=2m,where n=2”+Land0≤L<2”, A(n)-B(n)-Cn)=1; A(n)+C(n)=n
14 RECURRENT PROBLEMS by separating out its dependence on K, /3, and y, it seems that A(n) = 2m; B(n) = 2”‘-1-L; (1.14) C(n) = 1. Here, as usual, n = 2m + 1 and 0 < 1 < 2m, for n 3 1. It’s not terribly hard to prove (1.13) and (1.14) by induction, but the Ho/d onto your calculations are messy and uninformative. Fortunately there’s a better way hats, this next part to proceed, by choosing particular values and then combining them. Let’s is new stuff. illustrate this by considering the special case a = 1, (3 = y = 0, when f(n) is supposed to be equal to A(n): Recurrence (1.11) becomes A(1) = 1; A(2n) = 2A(‘n), for n 3 1; A(2n + 1) = 2A(n), for n 3 1. Sure enough, it’s true (by induction on m) that A(2” + 1) = 2m. Next, let’s use recurrence (1.11) and solution (1.13) in Teverse, by starting with a simple function f(n) and seeing if there are any constants (OL, 8, y) that will define it. Plugging in the constant function f(n) = 1 says that A neat idea! 1 = a; 1 = 2.1+p; 1 = 2.1+y; hence the values (a, 6, y) = (1, -1, -1) satisfying these equations will yield A(n) - B(n) - C(n) = f(n) = 1. Similarly, we can plug in f(n) = n: 1 = a; 2n = 2+n+ L3; 2n+l = 2.n+y; These equations hold for all n when a = 1, b = 0, and y = 1, so we don’t need to prove by induction that these parameters will yield f(n) = n. We already know that f(n) = n will be the solution in such a case, because the recurrence (1.11) uniquely defines f(n) for every value of n. And now we’re essentially done! We have shown that the functions A(n), B(n), and C(n) of (1.13), which solve (1.11) in general, satisfy the equations A(n) = 2”) where n = 2” + 1 and 0 6 1 < 2”; A(n) -B(n) - C(n) = 1 ; A(n) + C(n) = n
1.3 THE JOSEPHUS PROBLEM 15 Our conjectures in (1.14)follow immediately,since we can solve these equa- tions to get C(n)=n -A(n)=I and B(n)=A(n)-1 C(n)=2"-1 -L. Beware:The au This approach illustrates a surprisingly useful repertoire method for solv- thors are expecting ing recurrences.First we find settings of general parameters for which we us to fgure out the idea of the know the solution;this gives us a repertoire of special cases that we can solve. repertoire method Then we obtain the general case by combining the special cases.We need as from seat-of-the- many independent special solutions as there are independent parameters (in pants examples, instead of giving this case three,for a,B,and y).Exercises 16 and 20 provide further examples us a top-down of the repertoire approach. presentation.The We know that the original J-recurrence has a magical solution,in binary: method works best with recumrences J((bm bm-1...b1bo)2)=(bm-1...b1 bo bm)2,where bm=1. that are 'linear;in the sense that their solutions can be Does the generalized Josephus recurrence admit of such magic? expressed as a sum Sure,why not?We can rewrite the generalized recurrence (1.11)as of arbitrary param- eters multiplied by f1)=a, functions of n,as f2n+j)=2f(n)+Bi,forj=0,1andn≥1， (1.15) in (1.13).Equation (1.13)is the key. if we let Bo=B and B1=y.And this recurrence unfolds,binary-wise: f((bm bm-1...bibo)2)=2f((bm bm-1...b1)2)+Bbo =4f(bmbm-1.·.b22)+2Bb,+Bb =2mf((bm)2)+2m-B++2+Bbo =2mx+2m-Bbm-1+…+2Bb1+Bbg· ('relax='destroy)Suppose we now relax the radix 2 notation to allow arbitrary digits instead of just 0 and ]The derivation above tells us that f((bm bm-1..b1bo)2)=(a Bom-Bom-2...Bb BDo)2 (1.16) Nice.We would have seen this pattern earlier if we had written (1.12)in anot her way: n f(n) 1 X I think I get it: 2 2ox+β The binary repre- sentations of A(n), 3 2+Y B(n),and C(n) 4 have 1 's in different 4x+2β+B positions. 5 4x+28+y 6 4x+2y+B 7 4x+2Y+Y
Beware: The authors are expecting us to figure out the idea of the repertoire method from seat-of-thepants examples, instead of giving us a top-down presentation. The method works best with recurrences that are ‘linear” in the sense that /heir solutions can be expressed as a sum of arbitrary parameters multiplied by functions of n, as in (1.13). Equation (1.13) is the key. (‘relax = ‘destroy’) I think I get it: The binary representations of A(n), B(n), and C(n) have 1 ‘s in different positions. 1.3 THE JOSEPHUS PROBLEM 15 Our conjectures in (1.14) follow immediately, since we can solve these equations to get C(n) = n - A(n) = 1 and B(n) = A(n) - 1 - C(n) = 2” - 1 - 1. This approach illustrates a surprisingly useful repertoire method for solving recurrences. First we find settings of general parameters for which we know the solution; this gives us a repertoire of special cases that we can solve. Then we 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 01, J3, and y). Exercises 16 and 20 provide further examples of the repertoire approach. We know that the original J-recurrence has a magical solution, in binary: J(bn bm-1 . . . bl bob) = (bm-1 . . . b, bo b,)z , where b, = 1. Does the generalized Josephus recurrence admit of such magic? Sure, why not? We can rewrite the generalized recurrence (1.11) as f(1) = a; f(2n + j) = 2f(n) + J3j , for j = 0,l and n 3 1, (1.15) if we let BO = J3 and J31 = y. And this recurrence unfolds, binary-wise: f(bnbm-1 . . . bl bob) = 2f((bm b-1 . . . b, 12) + fib0 = 4f((b, b,el . . . Wz) + 2f’b, + fib‘, = 2mf((bmh) +2m-1Pbmm, +.“+@b, + (3bo = 2”(x + 293b,m, + “’ + 2(&q + &, . Suppose we now relax the radix 2 notation to allow arbitrary digits instead of just 0 and 1. The derivation above tells us that f((bm b-1 . . bl bob) = (01 fib,-, Pb,,mz . . . @b, f’bo 12 . (1.16) Nice. We would have seen this pattern earlier if we had written (1.12) in anot her way: