Circle Cutting

$\begin{figure}\begin{center}\BoxedEPSF{CircleCutting.epsf scaled 1200}\end{center}\end{figure}$

Determining the maximum number of pieces in which it is possible to divide a Circle for a given number of cuts is called the circle cutting, or sometimes Pancake Cutting, problem. The minimum number is always , where is the number of cuts, and it is always possible to obtain any number of pieces between the minimum and maximum. The first cut creates 2 regions, and the th cut creates new regions, so

$\displaystyle f(1)$	$\textstyle =$	$\displaystyle 2$	(1)
$\displaystyle f(2)$	$\textstyle =$	$\displaystyle 2+f(1)$	(2)
$\displaystyle f(n)$	$\textstyle =$	$\displaystyle n+f(n-1).$	(3)

Therefore,

$\displaystyle f(n)$	$\textstyle =$	$\displaystyle n+[(n-1)+f(n-2)]$
	$\textstyle =$	$\displaystyle n+(n-1)+\ldots+2+f(1) = f(1)+\sum_{k=2}^n k f(1)$
	$\textstyle =$	$\displaystyle 2+{\textstyle{1\over 2}}(n+2)(n-1)$
	$\textstyle =$	$\displaystyle {\textstyle{1\over 2}}(n^2+n+2).$	(4)

Evaluating for

, 2, ... gives 2, 4, 7, 11, 16, 22, ... (Sloane's A000124).

$\begin{figure}\begin{center}\BoxedEPSF{CircleCuttingCircumference.epsf}\end{center}\end{figure}$

A related problem, sometimes called Moser's Circle Problem, is to find the number of pieces into which a Circle is divided if points on its Circumference are joined by Chords with no three Concurrent. The answer is

$\displaystyle g(n)$	$\textstyle =$	$\displaystyle {n\choose 4}+{n\choose 2}+1$	(5)
	$\textstyle =$	$\displaystyle {\textstyle{1\over 24}}(n^4-6n^3+23n^2-18n+24),$	(6)

(Yaglom and Yaglom 1987, Guy 1988, Conway and Guy 1996, Noy 1996), where ${n\choose m}$ is a Binomial Coefficient. The first few values are 1, 2, 4, 8, 16, 31, 57, 99, 163, 256, ... (Sloane's A000127). This sequence and problem are an example of the danger in making assumptions based on limited trials. While the series starts off like $2^{n-1}$ , it begins differing from this Geometric Series at

References

Conway, J. H. and Guy, R. K. ``How Many Regions.'' In The Book of Numbers. New York: Springer-Verlag, pp. 76-79, 1996.

Guy, R. K. ``The Strong Law of Small Numbers.'' Amer. Math. Monthly 95, 697-712, 1988.

Noy, M. ``A Short Solution of a Problem in Combinatorial Geometry.'' Math. Mag. 69, 52-53, 1996.

Sloane, N. J. A. Sequences A000124/M1041 and A000127/M1119 in ``An On-Line Version of the Encyclopedia of Integer Sequences.'' http://www.research.att.com/~njas/sequences/eisonline.html and Sloane, N. J. A. and Plouffe, S. The Encyclopedia of Integer Sequences. San Diego: Academic Press, 1995.

Yaglom, A. M. and Yaglom, I. M. Problem 47. Challenging Mathematical Problems with Elementary Solutions, Vol. 1. New York: Dover, 1987.