Recursion Formula. How Many Slices

HS PUMP. Fall 2009 CSUN Math How many slices? ¶ 1. Three straight cuts of a pizza pie right through the center of the pie make six slices. But if you slightly displace one of the cuts so that it does not go through the middle, then you obtain seven pieces. What is the largest number of pieces of pizza that you can make with n straight cuts through a pizza pie? ¶ 2. The problem is to maximize the number of pieces that we can obtain with n cuts. This is a typical problem in discrete mathematics. We can sketch a few diagrams and find the number of pieces for small values of the number of cuts. For example, if no cut is done, then there is just one piece, the whole pizza. We can not do better than that, so we write P(0) = 1. Equally as easy is the case in which only one cut is to be done. Two pieces result from one cut, so P(n) = 2. We do not worry about the cut being a fair cut, that is, whether one of the two pieces is smaller than the other. When doing three cuts things start to get interesting. If the three cuts all go through a common point on the pizza top, then only six pieces result. But if you move your knife slightly before doing the final third cut, then you can get seven pieces. That is, P(3) = 7. ¶ 3. Use the diagrams below to find the values P(4) and P(5), the maximum number of pieces of pizza that can be obtained when doing 4 cuts and when doing 5 cuts. September 22, 2009 1 HS PUMP. Fall 2009 CSUN Math How many slices? ¶ 4. After finding P(4) and P(5), sketch below one of the optimal configurations for pizza cutting. ¶ 5. With a little more difficulty and a little more work we can fill in the values for P(n) in the table below: n number of cuts 0 1 2 3 4 5 6 7 P(n) max number of pieces ¶ 6. As you work out more and more values for P(n), you will notice the following basic principle an optimal configuration satisfies: If a configuration of pizza cuts produces a maximum number of pieces, then each cut crosses every other cut (no parallel cuts), and no three cuts cross at the same point. ¶ 7. You would also notices that when trying to compute one value, say P(6), you try to add one more cut to a configuration with 5 cuts that gives the maximum value P(5). It turns out that there is a formula that relates any value P(n) to the previous value P(n − 1). The formula is P(n) = P(n − 1) + n This is called a recursion formula: To find the value P(8) for example, we compute P(0) = 1 P(1) = P(0) + 1 = 2 P(2) = P(3) = P(4) = P(5) = P(6) = P(7) = P(8) = The reason for the recurrence formula P(n) = P(n − 1) + n to hold true is as follows. Suppose that you start with n − 1 cuts that give the maximum value P(n − 1). Then try to add one more cut to form the P(n) pieces. According to the basic principle, your last cut must cut each of the previous n − 1 cuts. Each time you do so, one more piece is added: a total of n − 1 pieces, and then there is one more piece formed when you finish the cut at the border of the piece, thus making a total of n more pieces. September 22, 2009 2 HS PUMP. Fall 2009 CSUN Math How many slices? ¶ 8. The recurrence formula P(n) = P(n − 1) + n can be solved. That is, there is a closed expression for P(n). To see this, replace P(n − 1) with P(n − 1) = P(n − 1) + (n − 1) like so: P(n) = P(n − 1) + n = P(n − 2) + (n − 1) + n Next replace P(n − 2) with P(n − 3) + (n − 2) to get P(n) = P(n − 3) + (n − 2) + (n − 1) + n and so on. It is much more clear to list all recurrences from n down to 1, like this: P(n) = P(n − 1) + n P(n − 1) = P(n − 2) + (n − 1) ··· = ··· P(3) = P(2) + 3 P(2) = P(1) + 2 P(1) = P(0) + 1 If you add all these equations and then cancel common terms on both sides of the equal sign, you would end up with the simplified expression: P(n) = P(0) + 1 + 2 + 3 + · · · + (n − 1) + n. If you now remember that 1 + 2 + 3 + ··· + n = n(n + 1) 2 then P(n) = ¶ 9. If you have forgotten the formula 1 + 2 + 3 + · · · + n = memory (in the figure, n = 10). n(n + 1) , the following figure will help your 2 11 00 00 00 00 00 00 00 00 00 00 00 11 11 00 11 11 00 11 11 00 11 11 00 11 11 00 11 11 00 11 11 00 11 11 00 11 11 00 11 00 11 00 11 00 11 00 11 00 11 00 11 00 11 00 11 00 00 11 11 00 11 00 11 00 11 00 11 00 11 00 11 00 11 00 11 00 11 11 00 11 00 11 00 11 00 11 00 11 00 11 00 00 11 11 00 11 00 11 00 11 00 11 00 11 00 11 00 00 11 00 11 00 11 00 11 00 11 00 11 00 00 11 11 00 11 00 11 00 11 00 11 00 11 00 11 00 11 00 00 00 00 00 00 11 11 00 11 11 00 11 11 00 11 11 00 11 11 00 11 00 11 11 00 11 00 00 11 00 00 11 00 11 11 00 11 00 11 00 11 00 11 00 00 00 00 11 11 00 11 11 00 11 11 00 11 00 11 11 00 11 00 00 11 11 00 11 00 00 11 00 00 11 11 00 11 00 11 00 11 September 22, 2009 3 HS PUMP. Fall 2009 CSUN Math How many slices? ¶ 10. The calculus of finite differences provides another technique to obtain the formula for P(n) from the first few values. For that, you first write the numbers n = 0, 1, 2, 3, · · · for which you have found P(n). Under those numbers, you write the value of P(n), like this n P(n) 1st differences 0 1 1 2 2 4 3 7 4 11 5 16 6 22 7 ··· 1 2nd differences 3rd differences Then you compute the 1st differences, then the second differences, that is, the differences of the differences, and so on, until you reach a row of differences with all numbers equal. In this example, this happens with the row of 2nd differences: all second differences are 1’s. This means that your formula for P(n) should be a polynomial of degree 2 like P(n) = An2 + Bn + C. To find A, B, and C, you plug the values n = 1, 2, 3 into An2 + Bn + c and obtain the following system of equations: P(0) = 1 = C P(1) = 2 = A + B + C P(2) = 4 = 4A + 2B + C This is a linear system with 3 equations and 3 unknowns, A, B, and C. Can you solve it? September 22, 2009 4 HS PUMP. Fall 2009 CSUN Math How many slices? ¶ 11. The method for finding an algebraic expression for the number of pieces of pizza P(n) given a few initial values P(0) = 1, P(1) = 2, works also for other sequences which have a polynomial general formula. Here are some problems for you to practice with this method. Find polynomial formulas p(N) that give the following sets of numbers corresponding to N = 0, 1, 2, 3, 5, · · · : 1. 0, 0, 6, 24, 60, 120. 2. 0, 1, 4, 10, 20, 35. 3. 0, −1, 4, 27, 80, 175. ¶ 12. Find short expressions for the following (N denotes a whole number): 1. 1 + 3 + 5 + 7 + · · · + (2N − 1). 2. 12 + 32 + 52 + · · · + (2N − 1)2 . 3. 03 + 13 + 23 + · · · + N3 . ¶ 13. Find an expression c(N) for the number of regions into which the plane is divided by N circles arraged so that any two intersect in two points and no three have a point in common. No circles, 1 region 1 circle, 2 regions 2 circles, 4 regions 3 circles, 8 regions Literature [1] T. S. Michael, How to guard an art gallery, Johns Hopkins [2] Online Encyclopedia of Integer Sequences at http://www.research.att.com/ njas/sequences/ September 22, 2009 5