4. Candy bars (3 points)

Beeblebrox has a candy bar with n squares. The candy bar is in the shape of an n × 1 rectangle, with n ? 1

grooves between the squares. Beeblebrox wants to break the candy bar into n squares, by breaking a piece

along one of its grooves. Each break takes a piece of k squares and breaks it into two pieces, one piece consisting

of a squares and a second piece consisting of the remaining k ? a squares, for some 0 < a < k. Beeblebrox

uses exactly n ? 1 breaks in total.

This is though a game, and Beeblebrox earns points each time he breaks a piece, and Beeblebrox wants to earn

as many points as possible. If Beeblebrox breaks a piece of k squares into two pieces of a and k ? a squares,

then Beeblebrox earns max{a, k ? a} points. (max{x, y} = x if x > y, and otherwise max{x, y} = y.)

1. Suppose that Beeblebrox applies the following strategy T : (1) Repeatedly, n ? 1 times, he takes the

remaining candy bar and break off exactly one piece. Let T(n) denote the total number of points that

Beeblebrox earns, if he starts with a candy bar with n squares. Then we can formulate a recurrence

that measures the total number of points Beeblebrox earns: T(n) = (n ? 1) + T(n ? 1) for n > 1, and

T(1) = 0. Give a closed form for this recurrence, and briefly justify your answer. (No proof is required.)

2. Suppose now that Beeblebrox instead applies the following different strategy S: (2) Beeblebrox takes

any of remaining pieces, and breaks it as evenly as possible. E.g., if a piece has 17 squares, he breaks it

into a piece of 8 squares and another of 9 squares. He repeats this n?1 times, resulting in n pieces, each

consisting of exactly one square. Let S(n) denote the total number of points that Beeblebrox earns, if

he starts with a candy bar with n squares.

(i) Formulate a recurrence S(n) for the strategy S. (You are not asked to solve the recurrence, only to

formulate a recurrence.) Justify your recurrence. (ii) Prove that S(n) ? T(n) by mathematical induction

on n. (Note that a proof by mathematical induction is required.)