6.042/18.] Mathematics for Computer Science March 15.2005 Srini devadas and Eric Lehman Lecture notes Sums, Approximations, and Asymptotics II 1 Block Stacking How far can a stack of identical blocks overhang the end of a table without toppling over? Can a block be suspended entirely beyond the tables edge? Table Physics imposes some constraints on the arrangement of the blocks. In particular, the stack falls off the desk if its center of mass lies beyond the desk's edge. Moreover, the center of mass of the top k blocks must lie above the(k+ 1)-st block; otherwise, the top k would fall over In order to find the best configuration of blocks satisfying these constraints, we'll need a fact about centers of mass Fact 1. If two objects have masses m1 and m2 and centers-of-mass at positions a1 and 22, center of mass of the two objects together is at position 31m1+2m2 m1+m2 Define the offset of a particular configuration of blocks to be the horizonal distar from its center of mass to its rightmost edge offset center of mass Table
6.042/18.062J Mathematics for Computer Science March 15, 2005 Srini Devadas and Eric Lehman Lecture Notes Sums, Approximations, and Asymptotics II 1 Block Stacking How far can a stack of identical blocks overhang the end of a table without toppling over? Can a block be suspended entirely beyond the table’s edge? Table Physics imposes some constraints on the arrangement of the blocks. In particular, the stack falls off the desk if its center of mass lies beyond the desk’s edge. Moreover, the center of mass of the top k blocks must lie above the (k + 1)st block; otherwise, the top k would fall over. In order to find the best configuration of blocks satisfying these constraints, we’ll need a fact about centers of mass. Fact 1. If two objects have masses m1 and m2 and centersofmass at positions z1 and z2, then the center of mass of the two objects together is at position: z1m1 + z2m2 m1 + m2 Define the offset of a particular configuration of blocks to be the horizonal distance from its center of mass to its rightmost edge. offset ? center of mass - s ? Table
2 Sums, Approximations, and Asymptotics Il The offset determines precisely how far that configuration can extend beyond the desk since at best the center of mass lies right above the desks edge. So hereafter we can focus on maximizing the offset of a stack of n blocks rather than the overhang. As a result, we need only be concerned with whether the stack is internally stable and not with whether the whole configuration is too far to the right and falls off the table We can establish the greatest possible offset of a stack of n blocks with an inductive argument. This is an instance where induction not only serves as a proof technique, but lso turns out to be a nice tool for reasoning about the problem Theorem 1. The greatest possible offset of a stack of n> 1 blocks 246 Proof. We use induction on n, the number of blocks. Let P(n) be the proposition that the greatest possible offset of a stack of n> 1 blocks is 1/2+1/4+..+1/(2n) Base case: For a single block, the center of mass is distance X1= 1/2 from its rightmost edge. So the offset is 1/2 and P(1)is true Inductive step: For n> 2, we assume that P(n-1) is true in order to prove P(n). A stack of n blocks consists of the bottom block together with a stack of n-1 blocks on top In order to acheive the greatest possible offset with n blocks the top n-1 blocks should themselves have the greatest possible offset, which is Xn-i; otherwise, we could do better by replacing the top n- l blocks with a different configuration that has greater offset Furthermore, the center of mass of the top n-1 blocks should lie directly above the right edge of the bottom block; otherwise, we could do better by sliding the top n-1 blocks farther to the right n-1 blocks Weve now identified the configuration of n blocks with the greatest possible offset What remains is to determine what that offset is. To that end, we'll apply Fact 1 where positions are measured relative to the rightmost edge of the n-block stack. In particular, 1 blocks with center of mass at position Xn-I, and 1 block wit at position Xn-1+2. So Fact 1 implies that the maximum possible offset of a stack of n
2 Sums, Approximations, and Asymptotics II The offset determines precisely how far that configuration can extend beyond the desk since at best the center of mass lies right above the desk’s edge. So hereafter we can focus on maximizing the offset of a stack of n blocks rather than the overhang. As a result, we need only be concerned with whether the stack is internally stable and not with whether the whole configuration is too far to the right and falls off the table. We can establish the greatest possible offset of a stack of n blocks with an inductive argument. This is an instance where induction not only serves as a proof technique, but also turns out to be a nice tool for reasoning about the problem. Theorem 1. The greatest possible offset of a stack of n ≥ 1 blocks is: 1 1 1 1 Xn = + + + . . . + 2 4 6 2n Proof. We use induction on n, the number of blocks. Let P(n) be the proposition that the greatest possible offset of a stack of n ≥ 1 blocks is 1/2 + 1/4 + . . . + 1/(2n). Base case: For a single block, the center of mass is distance X1 = 1/2 from its rightmost edge. So the offset is 1/2 and P(1) is true. Inductive step: For n ≥ 2, we assume that P(n − 1) is true in order to prove P(n). A stack of n blocks consists of the bottom block together with a stack of n − 1 blocks on top. In order to acheive the greatest possible offset with n blocks, the top n−1 blocks should themselves have the greatest possible offset, which is Xn−1; otherwise, we could do better by replacing the top n − 1 blocks with a different configuration that has greater offset. Furthermore, the center of mass of the top n − 1 blocks should lie directly above the right edge of the bottom block; otherwise, we could do better by sliding the top n − 1 blocks farther to the right. n − 1 blocks s Xn−1 - s Xn−1 + 1 - 2 We’ve now identified the configuration of n blocks with the greatest possible offset. What remains is to determine what that offset is. To that end, we’ll apply Fact 1 where positions are measured relative to the rightmost edge of the nblock stack. In particular, we have n−1 blocks with center of mass at position Xn−1, and 1 block with center of mass at position Xn−1 + 1 . So Fact 1 implies that the maximum possible offset of a stack of n 2
Sums, Approximations, and Asymptotics T blocks is (n-1)+(Xn-1+) X 1.1.1 We use the assumption P(n-1) in the last step. This proves P(n) The theorem follows by the principle of induction 1.1 Harmonic numbers Sums similar to the one in Theorem 1 come up all the time in computer science. In partic is called a harmonic sum. Its value is called the n-th harmonic number and is denoted Hn In these terms, the greatest possible offset of a stack of n blocks is Hn We can tabulate the maximum achievable overhang with n= 1, 2, 3 and 4 blocks by computing the first few harmonic numbers of blocks maximum overhang 2H2=是(+)= H3=是(+是+)= 是H4=是(+++1)=2 The last line reveals that we can suspend the fourth block beyond the edge of the table Here's the configuration that does the trick
Sums, Approximations, and Asymptotics II 3 blocks is: 1 2 ) 1· Xn = Xn−1 · (n − 1) + (Xn−1 + n 1 = Xn−1 + 2n 1 1 1 1 = + + + . . . + 2 4 6 2n We use the assumption P(n − 1) in the last step. This proves P(n). The theorem follows by the principle of induction. 1.1 Harmonic Numbers Sums similar to the one in Theorem 1 come up all the time in computer science. In particular, 1 1 1 1 + + + . . . + 1 2 3 n is called a harmonic sum. Its value is called the nth harmonic number and is denoted Hn. In these terms, the greatest possible offset of a stack of n blocks is 1 2Hn. We can tabulate the maximum achievable overhang with n = 1, 2, 3 and 4 blocks by computing the first few harmonic numbers: # of blocks maximum overhang 1 1 2 1 1 1 2 1 H1 = ( ) = 2 1 1 2 1 1 3 4 2 H2 = ( + ) = 2 1 2 1 1 2 1 1 1 11 = 12 3 H3 = ( + + ) 2 1 2 3 1 1 2 1 1 1 1 25 4 H4 = ( + + + ) = > 1 2 1 2 3 4 24 1 2 1 4 1 6 1 8 The last line reveals that we can suspend the fourth block beyond the edge of the table! Here’s the configuration that does the trick:
Sums, Approximations, and Asymptotics II 1.2 Bounding a Sum with an Integral We need to know more about harmonic sums to determine what can be done with a large number of blocks. Unfortunately, there is no closed form for H, But, on the bright side we can get good lower and upper bounds on harmonic sums using a general technique involving integration that applies to many other sums as well Here's how it works. First, we imagine a bar graph where the area of the k-th bar is equal to the k-th term in the sum. In particular, each bar has width 1 and height equal to the value of the k-th term. For example, the bar graph corresponding to the harmonic sum 111 2+3 is shown below 1 1/2 1 01234 Now the value of the sum is equal to the area of the bars, and we can estimate the area of the bars using integration. Suppose we draw a smooth curve that runs just below the bars; in fact, there's a natural choice: the curve described by the function y= 1/(a+1) 1/2 =1/(x+1) 1
4 Sums, Approximations, and Asymptotics II 1.2 Bounding a Sum with an Integral We need to know more about harmonic sums to determine what can be done with a large number of blocks. Unfortunately, there is no closed form for Hn. But, on the bright side, we can get good lower and upper bounds on harmonic sums using a general technique involving integration that applies to many other sums as well. Here’s how it works. First, we imagine a bar graph where the area of the kth bar is equal to the kth term in the sum. In particular, each bar has width 1 and height equal to the value of the kth term. For example, the bar graph corresponding to the harmonic sum 1 1 1 1 Hn = + + + . . . + 1 2 3 n is shown below. 6 1 1/2 1 1 1 1 . . . 1 2 3 4 - 0 1 2 3 4 n − 1 n Now the value of the sum is equal to the area of the bars, and we can estimate the area of the bars using integration. Suppose we draw a smooth curve that runs just below the bars; in fact, there’s a natural choice: the curve described by the function y = 1/(x + 1). - 6 1 1 1 2 1 3 1 4 1 1/2 y = 1/(x + 1) 0 1 2 3 4 n − 1 n
ums, Approximations, and Asymptotics Il The area of the bars is at least the area under this curve so we have a lower bound on the n-th harmonic sum 111 (n+1) Remember that n blocks can overhang the edge of a table by Hn block wi we had, say, a million blocks, then this lower bound implies that we could achieve an overhang of at least 1m(.00069 block widths! In fact, since the lower bound of In(n+ 1) grows arbitrarily large, there is no limit on how far the stack can overhang. Of course, this assumes no breeze, defor- mation of the blocks, or gravitational variation as our stack grows thousands of miles high We can get an upper bound on the n-th harmonic number by playing essentially the same game. Now we need a curve that skims just above the bar graph. The curve defined by y=1/a fits the bill 1/2 01234 1n2 The area under this curve is an upper bound on the area of the bar graph and thus on the n-th harmonic sum. But there's a problem: the area under the curve is infinite because y=1/ has a bad asymptote at =0. This is a common problem when bounding sums with integrals and there's a simple solution: take the exact value of the first term(1/1)and then bound the remaining terms(1/2+1/3+..+1/n) with an integral. In this case, we
Sums, Approximations, and Asymptotics II 5 The area of the bars is at least the area under this curve, so we have a lower bound on the nth harmonic sum: 1 1 1 1 Hn = + + + . . . + � 1 2 3 n n 1 ≥ dx 0 x + 1 = ln(n + 1) Remember that n blocks can overhang the edge of a table by 1 2Hn block widths. So if we had, say, a million blocks, then this lower bound implies that we could achieve an overhang of at least ln(1, 000, 000 + 1) = 6.907 . . . 2 block widths! In fact, since the lower bound of 1 2 ln(n + 1) grows arbitrarily large, there is no limit on how far the stack can overhang. Of course, this assumes no breeze, deformation of the blocks, or gravitational variation as our stack grows thousands of miles high. We can get an upper bound on the nth harmonic number by playing essentially the same game. Now we need a curve that skims just above the bar graph. The curve defined by y = 1/x fits the bill. - 6 1 1 1 2 1 3 1 4 1 1/2 y = 1/x 0 1 2 3 4 n − 1 n The area under this curve is an upper bound on the area of the bar graph and thus on the nth harmonic sum. But there’s a problem: the area under the curve is infinite because y = 1/x has a bad asymptote at x = 0. This is a common problem when bounding sums with integrals and there’s a simple solution: take the exact value of the first term (1/1) and then bound the remaining terms (1/2 + 1/3 + . . . + 1/n) with an integral. In this case, we