16 RECURRENT PROBLEMS For example,when n 100 =(1100100)2,our original Josephus values a=1,B=-1,and y =1 yield n=(1100100)2 100 f(n)=(11-1-11-1-1)2 =+64+32-16-8+4-2-1=73 as before.The cyclic-shift property follows because each block of binary digits (10...00)2 in the representation of n is transformed into (1.··-1-12=(00.012. So our change of notation has given us the compact solution (1.16)to the There are two general recurrence (1.15).If we're really uninhibited we can now generalize kinds of general- izations.One Is even more.The recurrence cheap and the other is valuable. f6j)=, or1≤j<d (1.17) It is easy to gen- f(dn +j)=cf(n)+Bi, for0≤j<d a n d n≥l, eralize by diluting a little idea with a is the same as the previous one except that we start with numbers in radix d big terminology. It is much more and produce values in radix c.That is,it has the radix-changing solution difficult to pre- pare a refined and f((bm bm-1...b1 bo)a)=(aom Bom-1Bom-2...Bbi Bbo)c. (1.18) condensed extract fom several good For example,suppose that by some stroke of luck we're given the recurrence ingredients. -G.P61ya238 f(1)=34, f(2)=5, f(3n)=10fn)+76, forn≥1， f(3n+1)=10f(m)-2, forn≥l, f(3n+2)=10fn)+8, forn≥1， and suppose we want to compute f (19).Here we have d 3 and c=10.Now Perhaps this was a 19 =(201)3,and the radix-changing solution tells us to perform a digit-by- stroke of bad luck. digit replacement from radix 3 to radix 10.So the leading 2 becomes a 5,and the 0 and 1 become 76 and -2,giving f(19)=f(201)3)=(576-210=1258。 which is our answer. But in general I'm Thus Josephus and the Jewish-Roman war have led us to some interesting against recurences general recurrences. of war
16 RECURRENT PROBLEMS For example, when n = 100 = (1100100)~, our original Josephus values LX=], /3=-l,andy=l yield n= (1 1 0 0 1 0 O)L = 100 f(n) = ( 1 1 -1 -1 1 -1 -1)1 =+64+32-16-8+4-2-l = 7 3 as before. The cyclic-shift property follows because each block of binary digits (10 . . . 00)~ in the representation of n is transformed into (l-l . . . -l-l)2 = (00 ..,Ol)z. So our change of notation has given us the compact solution (1.16) to the There are two general recurrence (1.15). If we’re really uninhibited we can now generalize kinds Ofgenera’- even more. The recurrence izations. One is cheap and the other f(i) = aj , for 1 < j < d; is valuable. (1.17) It is easy to genf(dn + j) = cf(n) + (3j , forO<j<d and n31, eralize by diluting a little idea with a is the same as the previous one except that we start with numbers in radix d big terminology. and produce values in radix c. That is, it has the radix-changing solution It is much more dificult to prepare a refined and f( bn b-1 . . .bl b&i) = cab, f’b,m, fib,-> . . . bb, (3bo)c. (1.18) condensed extract from several good For example, suppose that by some stroke of luck we’re given the recurrence ingredients. - G. Pdlya 12381 f(1) = 34, f(2) = 5, f(3n) = lOf(n) + 76, for n 3 1, f(3nfl) = lOf(n)-2, for n 3 1, f(3n +2) = lOf(n)+8, for n 3 1, and suppose we want to compute f (19). Here we have d = 3 and c = 10. Now Perhaps this was a 19 = (201)3, and the radix-changing solution tells us to perform a digit-by- stroke Of bad luck. digit replacement from radix 3 to radix 10. So the leading 2 becomes a 5, and the 0 and 1 become 76 and -2, giving f(19) = f((201)3) = (5 76 -2),. = 1258, which is our answer. But in general I’m Thus Josephus and the Jewish-Roman war have led us to some interesting against recurrences general recurrences. of war
1 EXERCISES 17 Exercises Warmups Please do all the 1 All horses are the same color;we can prove this by induction on the warmups in all the number of horses in a given set.Here's how:"If there's just one horse chapters! -The Mgm't then it's the same color as itself,so the basis is trivial.For the induction step,assume that there are n horses numbered 1 to n.By the induc- tion hypothesis,horses 1 through n-1 are the same color,and similarly horses 2 through n are the same color.But the middle horses,2 through n 1,can't change color when they're in different groups;these are horses,not chameleons.So horses 1 and n must be the same color as well,by transitivity.Thus all n horses are the same color;QED."What, if anything,is wrong with this reasoning? 2 Find the shortest sequence of moves that transfers a tower of n disks from the left peg A to the right peg B,if direct moves between A and B are disallowed.(Each move must be to or from the middle peg.As usual, a larger disk must never appear above a smaller one.) 3 Show that,in the process of transferring a tower under the restrictions of the preceding exercise,we will actually encounter every properly stacked arrangement of n disks on three pegs. 4 Are there any starting and ending configurations of n disks on three pegs that are more than 2n-1 moves apart,under Lucas's original rules? 5 A "Venn diagram"with three overlapping circles is often used to illustrate the eight possible subsets associated with three given sets: B Can the sixteen possibilities that arise with four given sets be illustrated by four overlapping circles? 6 Some of the regions defined by n lines in the plane are infinite,while others are bounded.What's the maximum possible number of bounded regions? 7 Let H(n)=J(n+1)-J(n).Equation (1.8)tells us that H(2n)=2,and H(2n+1)=J〔2n+2)-J2m+1)=(2n+1)-1)-(2n)+1)=2H(n)-2, for all n>1.Therefore it seems possible to prove that H(n)=2 for all n, by induction on n.What's wrong here?
1 EXERCISES 17 Exercises Warmups Please do all the 1 All horses are the same color; we can prove this by induction on the warmups in all the chapters! number of horses in a given set. Here’s how: “If there’s just one horse - The h4gm ‘t then it’s the same color as itself, so the basis is trivial. For the induction step, assume that there are n horses numbered 1 to n. By the induction hypothesis, horses 1 through n - 1 are the same color, and similarly horses 2 through n are the same color. But the middle horses, 2 through n - 1, can’t change color when they’re in different groups; these are horses, not chameleons. So horses 1 and n must be the same color as well, by transitivity. Thus all n horses are the same color; QED.” What, if anything, is wrong with this reasoning? 2 Find the shortest sequence of moves that transfers a tower of n disks from the left peg A to the right peg B, if direct moves between A and B are disallowed. (Each move must be to or from the middle peg. As usual, a larger disk must never appear above a smaller one.) 3 Show that, in the process of transferring a tower under the restrictions of the preceding exercise, we will actually encounter every properly stacked arrangement of n disks on three pegs. 4 Are there any starting and ending configurations of n disks on three pegs that are more than 2” - 1 moves apart, under Lucas’s original rules? 5 A “Venn diagram” with three overlapping circles is often used to illustrate the eight possible subsets associated with three given sets: Can the sixteen possibilities that arise with four given sets be illustrated by four overlapping circles? 6 Some of the regions defined by n lines in the plane are infinite, while others are bounded. What’s the maximum possible number of bounded regions? 7 Let H(n) = J(n+ 1) - J(n). Equation (1.8) tells us that H(2n) = 2, and H(2n+l) = J(2n+2)-J(2n+l) = (2J(n+l)-l)-(2J(n)+l) = 2H(n)-2, for all n 3 1. Therefore it seems possible to prove that H(n) = 2 for all n, by induction on n. What’s wrong here?
18 RECURRENT PROBLEMS Homework exercises 8 Solve the recurrence Q。=;Q1=β； Q n (1+Qn-1)/Qn-2,for n 1. Assume that Qn≠0 for all n≥0.Himt:Q4=(1+a)/B 9 Sometimes it's possible to use induction backwards,proving things from now that's a n to n 1 instead of vice versa!For example,consider the statement horse of a different color. P(n):x1,.,Xn≤ This is true when n 2,since (x1+x2)2-4x1x2=(x1-x2)2>0. a By setting Xn=(x1+...+xn-1)/(n 1),prove that P(n)im- plies P(n-1)whenever n 1. b Show that P(n)and P(2)imply P(2n). c Explain why this implies the truth of P(n)for all n. 10 Let Qn be the minimum number of moves needed to transfer a tower of n disks from A to B if all moves must be clockwise-that is,from A to B,or from B to the other peg,or from the other peg to A.Also let Rn be the minimum number of moves needed to go from B back to A under this restriction.Prove that Q.-{8x11.fn28 iR&R={8+0.1+1.fR0 if n=0; (You need not solve these recurrences;we'll see how to do that in Chap- ter 7.) 11 A Double Tower of Hanoi contains 2n disks of n different sizes,two of each size.As usual,we're required to move only one disk at a time, without putting a larger one over a smaller one. a How many moves does it take to transfer a double tower from one peg to another,if disks of equal size are indistinguishable from each other? b What if we are required to reproduce the original top-to-bottom order of all the equal-size disks in the final arrangement?[Hint: This is difficult-it's really a "bonus problem."] 12 Let's generalize exercise lla even further,by assuming that there are m different sizes of disks and exactly nk disks of size k.Determine A(n1,...,n,),the minimum number of moves needed to transfer a tower when equal-size disks are considered to be indistinguishable
18 RECURRENT PROBLEMS Homework exercises 8 Solve the recurrence Qo = 0~; QI = B; Qn = (1 + Qn-l)/Qn-2, for n > 1. Assume that Q,, # 0 for all n 3 0. Hint: QJ = (1 + oc)/(3. 9 Sometimes it’s possible to use induction backwards, proving things from now that’s a n to n - 1 instead of vice versa! For example, consider the statement horse of a different color. P(n) : x1 . . .x, 6 ( x1 +. . . + x, n n ) , ifxr ,..., x,30. This is true when n = 2, since (x1 +xJ)~ -4~1x2 = (x1 -xz)~ 3 0. a By setting x,, = (XI + ... + x,~l)/(n - l), prove that P(n) implies P(n - 1) whenever n > 1. b Show that P(n) and P(2) imply P(2n). C Explain why this implies the truth of P(n) for all n. 1 0 Let Q,, be the minimum number of moves needed to transfer a tower of n disks from A to B if all moves must be clockwise-that is, from A to B, or from B to the other peg, or from the other peg to A. Also let R, be the minimum number of moves needed to go from B back to A under this restriction. Prove that Qn= ;;,,,+l { , ;;;,;i Rn= 0 , i d +Qnp,+,, ;;;,;’ n (You need not solve these recurrences; we’ll see how to do that in Chapter 7.) 11 A Double Tower of Hanoi contains 2n disks of n different sizes, two of each size. As usual, we’re required to move only one disk at a time, without putting a larger one over a smaller one. a How many moves does it take to transfer a double tower from one peg to another, if disks of equal size are indistinguishable from each other? b What if we are required to reproduce the original top-to-bottom order of all the equal-size disks in the final arrangement? [Hint: This is difficult-it’s really a “bonus problem.“] 12 Let’s generalize exercise lla even further, by assuming that there are m different sizes of disks and exactly nk disks of size k. Determine Nnl,. . . , n,), the minimum number of moves needed to transfer a tower when equal-size disks are considered to be indistinguishable
1 EXERCISES 19 13 What's the maximum number of regions definable by n zig-zag lines, ZZ2=12 each of which consists of two parallel infinite half-lines joined by a straight segment? 14 How many pieces of cheese can you obtain from a single thick piece by making five straight slices?(The cheese must stay in its original position Good luck keep- while you do all the cutting,and each slice must correspond to a plane ing the cheese in in 3D.)Find a recurrence relation for P,,the maximum number of three- position. dimensional regions that can be defined by n different planes. 15 Josephus had a friend who was saved by getting into the next-to-last position.What is I(n),the number of the penultimate survivor when every second person is executed? 16 Use the repertoire method to solve the general four-parameter recurrence g(1)=c; g(2n+j)=3g(n)+yn+B;,for j=0,1 and n1. Hint:Try the function g(n)=n. Exam problems 17 If Wn is the minimum number of moves needed to transfer a tower of n disks from one peg to another when there are four pegs instead of three, show that Wnin+1)/26 2Wn(n-1)/2+Tn for n>0. (Here Tn=2"-1 is the ordinary three-peg number.)Use this to find a closed form f(n)such that Wn(n+1)/2 f(n)for all n >0. 18 Show that the following set of n bent lines defines Zn regions,whereZn is defined in(1.7:The jth bent line,.forl≤j≤n,has its zig at(n2i,0】 and goes up through the points (n2i-n,1)and (n2i-ni-n,1). 19 Is it possible to obtain Zn regions with n bent lines when the angle at each zig is30°？ Is this like a 20 Use the repertoire method to solve the general five-parameter recurrence five-star general recurrence? h(1)=a; h(2n+j)=4h(n)+Yn+β；，forj=0,1andn≥1. Hint:Try the functions h(n)=n and h(n)=n2
1 EXERCISES 19 13 What’s the maximum number of regions definable by n zig-zag lines, czzz=12 Good luck keeping the cheese in position. each of which consists of two parallel infinite half-lines joined by a straight segment? 14 How many pieces of cheese can you obtain from a single thick piece by making five straight slices? (The cheese must stay in its original position while you do all the cutting, and each slice must correspond to a plane in 3D.) Find a recurrence relation for P,, the maximum number of threedimensional regions that can be defined by n different planes. 15 Josephus had a friend who was saved by getting into the next-to-last position. What is I(n), the number of the penultimate survivor when every second person is executed? 16 Use the repertoire method to solve the general four-parameter recurrence g(l) = m; gVn+j) = h(n) +w+ Pi, for j = 0,l and n 3 1. Hint: Try the function g(n) = n. Exam problems 1 7 If W, is the minimum number of moves needed to transfer a tower of n disks from one peg to another when there are four pegs instead of three, show that Wn(n+1 j/2 6 34’n(n-1 i/2 + Tn 7 for n > 0. Is this like a five-star general recurrence? (Here T,, = 2” - 1 is the ordinary three-peg number.) Use this to find a closed form f(n) such that W,(,+r~,~ 6 f(n) for all n 3 0. 18 Show that the following set of n bent lines defines Z, regions, where Z, is defined in (1.7): The jth bent line, for 1 < j 6 n, has its zig at (nZi,O) and goes up through the points (n’j - nj, 1) and (n’j - ni - nn, 1). 19 Is it possible to obtain Z, regions with n bent lines when the angle at each zig is 30”? 20 Use the repertoire method to solve the general five-parameter recurrence h(l) = a; h(2n + i) = 4h(n) + yin + (3j , forj=O,l and n>l. Hint: Try the functions h(n) = n and h(n) = n2
20 RECURRENT PROBLEMS 21 Suppose there are 2n people in a circle;the first n are "good guys" and the last n are "bad guys!'Show that there is always an integer m (depending on n)such that,if we go around the circle executing every mth person,all the bad guys are first to go.(For example,when n =3 we can take m 5;when n=4 we can take m=30.) Bonus problems 22 Show that it's possible to construct a Venn diagram for all 2"possible subsets of n given sets,using n convex polygons that are congruent to each other and rotated about a common center. 23 Suppose that Josephus finds himself in a given position j,but he has a chance to name the elimination parameter q such that every qth person is executed.Can he always save himself? Research problems 24 Find all recurrence relations of the form X=+XL十…+aXm出 b1 Xn-1+..+bkXn-k whose solution is periodic. 25 Solve infinitely many cases of the four-peg Tower of Hanoi problem by proving that equality holds in the relation of exercise 17. 26 Generalizing exercise 23,let's say that a Josephus subset of (1,2,...,n is a set of k numbers such that,for some q,the people with the other n-k numbers will be eliminated first.(These are the k positions of the "good guys"Josephus wants to save.)It turns out that when n=9,three of the 29 possible subsets are non-Josephus,namely (1,2,5,8,9),(2,3,4,5,8), and (2,5,6,7,8).There are 13 non-Josephus sets when n=12,none for any other values of n 12.Are non-Josephus subsets rare for large n? Yes.and well done if you find them
20 RECURRENT PROBLEMS 21 Suppose there are 2n people in a circle; the first n are “good guys” and the last n are “bad guys!’ Show that there is always an integer m (depending on n) such that, if we go around the circle executing every mth person, all the bad guys are first to go. (For example, when n = 3 we can take m = 5; when n = 4 we can take m = 30.) Bonus problems 22 Show that it’s possible to construct a Venn diagram for all 2” possible subsets of n given sets, using n convex polygons that are congruent to each other and rotated about a common center. 23 Suppose that Josephus finds himself in a given position j, but he has a chance to name the elimination parameter q such that every qth person is executed. Can he always save himself? Research problems 24 Find all recurrence relations of the form x _ ao+alX,-1 +...+akXnPk n- bl X,-i + . . + bkXn-k whose solution is periodic. 25 Solve infinitely many cases of the four-peg Tower of Hanoi problem by proving that equality holds in the relation of exercise 17. 26 Generalizing exercise 23, let’s say that a Josephus subset of {1,2,. . . , n} is a set of k numbers such that, for some q, the people with the other n-k numbers will be eliminated first. (These are the k positions of the “good guys” Josephus wants to save.) It turns out that when n = 9, three of the 29 possible subsets are non-Josephus, namely {1,2,5,8,9}, {2,3,4,5, S}, and {2,5,6,7, S}. There are 13 non-Josephus sets when n = 12, none for any other values of n 6 12. Are non-Josephus subsets rare for large n? Yes, and well done if you find them