Mathematics for Computer Science

Chapter 14 Sums and Asymptotics416

1=2

table

center of mass

of block

Figure 14.5 One block can overhang half a block length.

14.4.2 A Recursive Solution

Our goal is to find a formula for the maximum possible spreadSnthat is achievable
with a stable stack ofnblocks.
We already know thatS 1 D 1=2since the right edge of a single block with
length 1 is always distance1=2from its center of mass. Let’s see if we can use a
recursive approach to determineSnfor alln. This means that we need to find a
formula forSnin terms ofSiwherei < n.
Suppose we have a stable stackSofnblocks with maximum possible spreadSn.
There are two cases to consider depending on where the rightmost block is in the
stack.

Case 1: The rightmost block inSis the bottom block. Since the center of mass
of the topn 1 blocks must be over the bottom block for stability, the spread is
maximized by having the center of mass of the topn 1 blocks be directly over the
leftedge of the bottom block. In this case the center of mass ofSis^7

.n1/
 1 C.1/
^12

n

D 1

1

2n

(^7) The center of mass of a stack of blocks is the average of the centers of mass of the individual
blocks.