19 of 100: Crazy Pizza Cuts

We can prove a general result by induction:

The maximum number of pieces you can divide a circular pizza into with $n$ cuts is $\dfrac{n^2+n+2}{2}$

Let $P_n$ is the maximum number of pieces you can divide a circular pizza into with $n$ cuts.

With 1 cut, a pizza will be divided in to 2 parts, so $P_1=2$ .

Each new line intersects other $n$ lines in one point and divides each previous region of space into two regions. Therefore each new line adds at most new $n+1$ regions and so we have: $P_{n+1}=P_n+n+1$

We can see that $P_n=\dfrac{n^2+n+2}{2}$ and hence $P_4=11$ .

This is a possible answer for $n=4$ .

Each line can only intersect any other line once at most. Each intersection closes the boundary of a new 'piece' - thus, if drawing the optimal solution, each new line should be drawn so it intersects every other line once at distinct positions. The nth line will create n new pieces when drawn: one for every intersection with the n-1 other lines, and one for reaching the circumference.

0 lines: 1 piece

1 line: 1 + 1 = 2 pieces

2 lines: 2 + 2 = 4 pieces

3 lines: 4 + 3 = 7 pieces

4 lines: 7 + 4 = 11 pieces

n lines: 1 + (1 + 2 + 3 + 4 + ... + n) = 1+ n(n+1)/2

I figured out the "correct" solution but kept thinking, a pizza has thickness, so by cutting it parallel to the surface, it could be divided into 8 pieces with 3 cuts and 15 pieces with 4 cuts... you should have stated more clearly that the cuts must be perpendicular to the surface.

Besides the approach mentioned by others, here is another way to look at it. We know, from Euler's characteristic equation, $V - E + F= 2$ where $V$ is the number of Vertices , $E$ is the number of edges and $F$ is the number of Faces. Now, to maximize the number of faces, we need to maximize $V$ and also minimize $E$ .

Consider, if we had only 2 lines, whatever configuration we use, both lines will intersect at max 1 point and thus one new vertex will be created.

For 2 lines, $V=5$ , $E=8$ and $F = 4+1$ which satisfies $5- 8 + 5 = 2$

Here, the number of faces equal to $4+1$ because we need to consider the area outside the pizza as 1.

If we had 3 lines, we can draw the third line such that either it passes through the intersection of other two lines or cut both lines.We get maximum faces when the line cuts the other two.

For 3 lines, $V=9$ , $E=15$ and $F = 7 + 1$ which satisfies $9-15+8 = 2$

Similarly in case of 4 lines, we can draw the line such that it cuts the maximum number of lines thus creating more vertices and it results in maximizing number of Faces.

For 4 lines, $V=14$ , $E=24$ and $F = 11+1$ which satisfies $14- 24 + 12 = 2$

The formula gives you exact result instantaneously but this helps in understanding the idea behind the solution. :-)

Links

Euler characteristic

Formula for Plane Graph

This is one of the possible answers...

The cool thing is that the same idea generalises to 3D and further, with which you could e.g. also solve the following problem proposed in Germany's Bundeswettbewerb Mathematik in 2016:

Each side face of a dodecahedron lies in a uniquely determined plane. Those planes cut the space in a finite number of disjoint regions. Find the number of such regions.

This is what the pizza looks like after slicing it...

To maximize the number of pieces, each line drawn must intersect every other line, and no three lines should intersect at one point. This is because the more intersections there are, there must be more pieces, as there will be more regions in between intersections. Following these rules, we can draw a circle and draw four lines. Counting the segments there are, we get the answer $\boxed{11}$ .

If you make one cut, then the pizza will be cut into 2. If you make two cuts, then the pizza will be cut into 4. If you make three cuts, then the pizza will be cut into 7. 2 +2 = 4 4+3=7. The pattern is: +2 +3 +4. So 7 plus four equals to 11.

For the first cut, you slice it into 2 pieces.

For the second cut, you want try to have this cut intersecting with all the previous cuts (There's 1). So you have increased 2 pieces.

For the third cut, you want to try to have this cut intersecting with all the previous cuts too (There's 2 of them). 3 pieces increased.

...

In general, the maximum pieces you can get after $n$ slices is

$2+(2+3+4+...+n)=1+\frac{n(n+1)}{2}=\frac{n^2+n+2}{2}$

When $n=4$ , you get $\boxed{11}$ of them.

Why is difficulty "Might Draw Blood"? It's so easy.

n-th cut can't cross more than n-1 cut lines. It cuts one more piece, so no more than n. Therefore n-th cut increases the number of pieces by up to n. And so on...

The problem is requesting the maximum number of regions a plane can be divided by $4$ lines. In order to achieve this maximum, there can't be a pair of parallel lines (otherwise rotating one of them forms at least another region and this would contradict the maximality of the number of regions).

There are n over 2 intersection points $\dfrac{n(n-1)}{2}$ and each of them corresponds to a region. Lines, of course, don't stop at intersection points, and define other (non closed) region: to account for them we can imagine drawing a straight line which gets $n$ cuts from the $n$ lines, dividing it in ${n+1}$ parts, with each of them corresponding to a region. So there are $\dfrac{n^2+n+2}{2}$ regions, which could be written beautifully using binomials.

We can generalise the problem to "In how many parts can a space be cut by $n$ planes at maximum"? I will now sketch the solution, which is analogous and based on the previous one (spoiler warning!): the intersection of three planes defines a point, which can be associated bijectively to a region. Then, the $n$ planes will cut an auxiliary plane in the maximum number of regions a plane can be cut by $n$ lines, as the intersection between two planes is a line (which will meet other lines on that plane).

The central polygonal numbers, also known as the Lazy Caterer's Sequence, helps give the maximum number of pieces a circle can be cut into with a certain number of straight cuts.

We can begin to find a formula for this by solving a recurrence relation for the total number of pieces after $n$ cuts as follows:

We start with $f(n)=n+f(n-1)$ . Expansion of this function gives us $f(n)=n+(n-1)+f(n-2)$ , which expands into $f(n)=n+(n-1)+(n-2)+f(n-3)$ , which expands repeatedly in the same format until we reach the resulting expanded function where the last $f(n)$ has been reduced to $0$ . Therefore, we have $f(n)=n+(n-1)+(n-2)+(n-3)+...+3+2+1+f(0)$ . We know that $f(0)=1$ , so $1$ is added in the final simplification of the completely expanded function above. Therefore, we have the function $f(n)=(1+2+3+4+5+...+(n-1)+n)+1$ , which simplifies to $f(n)=\frac{n(n+1)}{2}+1$ , and then simplifies to $f(n)=\frac{n^2+n+2}{2}$ , which is the Lazy Caterer's Formula.

Plugging in $n=4$ into the Lazy Caterer's Formula, we get $11$ as our final answer.

One interesting thing to note is the sequence formed for the Lazy Caterer method. The sequence is as follows:

$1, 2, 4, 7, 11, 16, 22, 29, 37, 46, 56, ...$

Notice anything? If we look closely at the sequence above, we can see that it follows a pattern such that for each of the triangular numbers $0, 1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...$ we add $1$ . This is no coincidence, however! Looking back at our method to find the Lazy Caterer's Formula and it's application to the problem, we can note that the formula for the $n$ th triangular number, $\frac{n(n+1)}{2}$ , was added to the result of the function $f(0)=1$ .

• When you have 0 cuts, that means you have 1 whole pizza. With 1 cut it becomes 2 slices and with 2 cuts it becomes it 4 slices. So we start to notice a pattern. With each cut, there is ( $x$ ) more slices. So if you continue the pattern you get 11 cuts. You can generalize this problem into ( $x^{2}$ +x+2)/2 for x cuts

We can easily find a recursion method f(n)=n+f(n-1), then we count f(3)=7 and we find f(4)=4+f(3)=3+7=11

Well i didn't know any formula for this, so I simply started making figure and all cases in my mind here is what i got: 1. Cutting with 1 line - 2 parts 2. Cutting with 2 lines: a. when both have 1 common point - 3 parts

b. when both have no common point - 4 parts

1. Cutting with 3 lines: a. when all 3 have 1 common point - 4 parts

b. when all 3 have 1 common point with 1 line at circumference - 4 parts

c. when 2 of them have a common point and 3 is not intersecting any of them - 4 parts

d. when 2 of them have a common point and 3 is intersecting any 1 of them - 5 parts

e. when all 3 lines make a triangle with 2 vertex on circumference and 1 within circle - 5 parts

f. when all 3 lines make a triangle with 1 vertex on circumference and 2 within circle - 6 parts

g. when all 3 lines make a triangle with all 3 vertex within circle - 7 parts

1. By the above methods we can see that number of parts is directly proportional to intersections within circle, so 4th line should be placed in such a way in fig 3(g) that it enhances number of parts toits fullest, so here it is - 11 parts

$f(n)= \frac{1}{2}(n^2+n+2)$ is the formula for cutting a circular pie with $n$ cuts.

Thus, $f(4)= \frac{1}{2}( 4^2+4+2) =11$