| == |
The lazy caterer's sequence, more formally known as the central polygonal numbers, describes the maximum number of pieces of a circle (a pancake or pizza is usually used to describe the situation) that can be made with a given number of straight cuts. For example, three cuts across a pancake will produce six pieces if the cuts all meet at a common point, but up to seven if they do not. This problem generalizes to higher dimensions, see arrangement of hyperplanes.
Pancake cut into seven pieces with three straight cuts. (*) Formula and Sequence The maximum number of pieces p that can be created with a given number of cuts n, where n \ge 0, is given by the formula
Using binomial coefficients, the formula can be expressed as
This sequence (sequence A000124 in OEIS), starting with n = 0, results in 1, 2, 4, 7, 11, 16, 22, 29, 37, 46, 56, 67, 79, 92, 106, 121, 137, 154, 172, 191, 211, ... Each number equals 1 plus a triangular number. Proof
Two cuts produce four pieces. When a circle is cut n times to produce the maximum number of pieces, represented as p = f(n), the n-th cut must be considered; the number of pieces before the last cut is f(n − 1), while the number of pieces added by the last cut is n. To obtain the maximum number of pieces, the n-th cut line should cross all the other previous cut lines inside the circle. Thus, the n-th line itself is cut in n − 1 places, and into n line segments. Each segment divides one piece of the (n − 1)-cut pancake into 2 parts, adding exactly n to the number of pieces. The new line can't have any more segments since it can only cross each previous line once. A cut line can always cross over all previous cut lines, as rotating the knife at a small angle around a point that is not an existing intersection will, if the angle is small enough, intersect all the previous lines including the last one added. Thus, the total number of pieces after n cuts is f(n) = n + f(n − 1). This recurrence relation can be solved. If f(n − 1) is expanded one term the relation becomes f(n) = n + (n − 1) + f(n − 2). Expansion of the term f(n − 2) can continue until the last term is reduced to f(0), thus, f(n) = n + (n − 1) + (n − 2) + ... + 1 + f(0). Since f(0) = 1, because there is one piece before any cuts are made, this can be rewritten as f(n) = 1 + (1 + 2 + 3 + ... + n). The sum of the arithmetic sequence is
Links * Eric W. Weisstein, Circle Division by Lines at MathWorld. * Lazy Caterer's Sequence at PlanetMath. Retrieved from "http://en.wikipedia.org/" |
|
.
}.
