3
$\begingroup$

The lazy caterer's problem is to figure out the maximum number of pieces formed by $n$ straight cuts of a pizza. Any time two cuts meet new pieces are generated, so for maximum number of pieces it makes sense that all possible meetings are present. My question is how can this be guaranteed to happen. The wikipedia article says that

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.

What would be a mathematical proof of the above fact?

Edit: One of the earlier answers which was deleted was as follows: Given $n-1$ lines in the plane all intersecting each other separately it is always possible to draw an $n$th line which too separately intersects the others by selecting an appropriately different slope for it then of the others. A circle may then be constructed containing all the intersections which can then be scaled to the size of desired pizza.

Was this argument correct? It seems so to me, and I am confused as to why it was deleted.

$\endgroup$
1
$\begingroup$

We call an arrangement of lines valid if each line intersects each other, all the intersections are distinct, and occur on the interior of the circle.

Given a valid arrangement of $n$ lines, we wish to place one more line to create a larger valid arrangement. Choose an anchor point $(x_0,y_0)$ for the new line, so that no existing intersection is on the vertical line $x=x_0$, or to its left.

We now consider all non-vertical lines through our anchor point $(y-y_0)=m(x-x_0)$, i.e. we vary the slope $m$. Each of the $n$ other lines will intersect perhaps some of those, and not intersect others. Specifically, each of the $n$ other lines fall into two cases, and in both cases we will assign to each line an open interval of values for $m$ for which the new line will intersect the existing line.

Type 1: If the line does not cross the vertical line $x=x_0$, then our new line will intersect the existing line on some closed interval $[a,b]$. The endpoints will occur on the boundary of the circle, so we take $(a,b)$ for our interval.

Type 2: If the line crosses the vertical line $x=x_0$, then our new line will intersect the existing line if $m$ is in $(-\infty,r]\cup [s,+\infty)$ for some real $r,s$. The endpoints $r,s$ will again occur on the boundary of the circle. Further, one of these two intervals corresponds to intersections to the left of $x=x_0$; we take the other one. Hence either $(-\infty,r)$ or $(s,+\infty)$ corresponds to slopes for the new line that intersect the existing line to the right of $x=x_0$. In effect, we erase everything to the left of $x=x_0$ as we will not use it.

Consider now the intervals as defined above for our existing lines: $(a_1,b_1), \ldots, (a_n, b_n)$. Choose $i,j$ so that $a_i=\max\{a_1,\ldots, a_n\}$ and $b_j=\min\{b_1,\ldots, b_n\}$. We claim that the interval $(a_i, b_j)$ is in the mutual intersection of all $n$ intervals. Suppose to the contrary that $(a_i, b_j)$ doesn't intersect with $(a_k, b_k)$. If $b_k\le a_i$ (resp. $a_k\ge b_j$), then the $i$'th line (resp. $j$'th line) and the $k$'th line violate the hypotheses -- either they don't intersect, or they intersect on the circle boundary, or to the left of $x=x_0$.

Now, we may choose any slope in $(a_i, b_j)$ to form our line, and get a new valid arrangement.

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

The following is a proof along the lines hinted at by the quoted Wikipedia article.

Assume that the Pizza is some convex open set $\Omega$ in the plane and that lines $g_k$ $\>(1\leq k\leq n)$ have been drawn such that all intersection points $p_{ik}:= g_i\wedge g_k$ $\>(i\ne k)$ are well defined and lie in $\Omega$. We have to prove that we can draw a new line $g_{n+1}$ such that all intersection points $g_{n+1}\wedge g_k$ $\>(1\leq k\leq n)$ are well defined and lie in $\Omega$ as well.

Choose a point $O\in g_n$ different from all $p_{nk}$ $\>(1\leq k<n)$. Let $g_\alpha$ be the line obtained by rotating $g_n$ around $O$ by the angle $\alpha$. Fix a $k<n$ for the moment. The point $p_{\alpha k}:=g_\alpha\wedge g_k$ is a continuous function of $\alpha$ for $|\alpha|\ll1$, and $p_{0k}=p_{nk}\in\Omega$. As $\Omega$ is open there is an $\epsilon_k>0$ such that $p_{\alpha k}\in\Omega$ as soon as $|\alpha|<\epsilon _k$. Choosing an $\alpha$ with $0<|\alpha|<\min_{1\leq k<n}\epsilon_k$ and putting $g_{n+1}:=g_\alpha$ then will do the job.

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

(This is essentially the answer posted and deleted by @MJD. I don't understand why it was deleted; I don't see anything wrong with it, except that he may have left out a small part of the argument.)

Draw $n$ nonparallel lines $L_1',\dots,L_n'$ in the plane; e.g., $n$ distinct lines through the origin.

Now draw lines $L_1,\dots,L_n$ so that $L_i$ is parallel to $L_i'$ and no three of the new lines are concurrent. This is easily done by drawing the new lines one at a time. If $L_1,\dots,L_k$ have already been drawn, they intersect in a finite number of points; from the infinite family of lines parallel to $L_{k+1}'$ choose a line $L_{k+1}$ which misses all those points.

Now we have $n$ lines $L_1,\dots,L_n$ such that no two are parallel and no three are noncurrent; they intersect in $\binom n2$ distinct points. Draw a circle which encloses all those points, and declare the radius of that circle to be the unit of length.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.