The paragraphing problem is: Given a set of

words w$\_1,...,$ w$\_$n with word lengths l$\_1,...,$ l$\_$n$,$ break the words

into consecutive groups, such that the sum of the lengths of

the words in each group is less than a fixed value K$.($We

will ignore the issue of putting spaces between words or

hyphenation; these are minor details.$)$ The words remain

in the original order, so the task is just to insert line breaks

to ensure that each line is less than length K$.$

The greedy algorithm for line breaking is to pack in as

many words as possible into each line, e$.$g$.,$ to put words

into a line one at a time until the length bound K is reached,

and break the line before the word w$\_$r that caused the the

bound to be exceeded.

Prove that the Greedy Algorithm is optimal in the sense

that it produces a paragraph with the smallest number of

lines. For a formal proof, induction is recommended. The

key to this problem is coming up with the right induction

hypothesis.