## Cutting The Cake

**Moderators:** jestingrabbit, Moderators General, Prelates

### Cutting The Cake

After finally discovering that my favourite web-comic has a forum, I now actually have a place to test out my puzzles before I give them to my friends.

Here's one that I came up with very quickly, but after a little work I'm still not entirely sure I have the best solution.

I have a cake in front of me, which my baker has very kindly iced to make a 12 by 12 grid, with each of the tiny cakelets enclosed by four lines of icing. The icing also goes around the edge. I'm going to make a number of cuts in my cake. Each cut must be a straight line and must start and finish at a corner on the icing grid. After I've made my cuts, I have 4 pieces. What is the maximium total number of pieces I can make with one more cut? The pieces can be of any size and shape, as long as there are four of them after n cuts and a lot more after n+1.

Here's some pictoral examples, with the left hand diagram showing some examples of legal cuts and the right hand one showing a solution which makes 8 in total. That isn't my best solution so far! I do also apoligise for the amazingly bad quality of the diagrams...

Here's one that I came up with very quickly, but after a little work I'm still not entirely sure I have the best solution.

I have a cake in front of me, which my baker has very kindly iced to make a 12 by 12 grid, with each of the tiny cakelets enclosed by four lines of icing. The icing also goes around the edge. I'm going to make a number of cuts in my cake. Each cut must be a straight line and must start and finish at a corner on the icing grid. After I've made my cuts, I have 4 pieces. What is the maximium total number of pieces I can make with one more cut? The pieces can be of any size and shape, as long as there are four of them after n cuts and a lot more after n+1.

Here's some pictoral examples, with the left hand diagram showing some examples of legal cuts and the right hand one showing a solution which makes 8 in total. That isn't my best solution so far! I do also apoligise for the amazingly bad quality of the diagrams...

This is, er, no offense but you are a robot, aren't you?

That's just, um, beautiful, beautiful beautiful... just beautiful.

One hot summer's night Lorraine said: "It's time for you to see the lighthouse"

Dr. Ivanovich, was it really necessary?

That's just, um, beautiful, beautiful beautiful... just beautiful.

One hot summer's night Lorraine said: "It's time for you to see the lighthouse"

Dr. Ivanovich, was it really necessary?

- Cosmologicon
**Posts:**1806**Joined:**Sat Nov 25, 2006 9:47 am UTC**Location:**Cambridge MA USA-
**Contact:**

### Re: Cutting The Cake

That's interesting, but I don't understand the rules, I think. It looks to me like most of your cuts on the right-hand diagram don't start and end at grid points.

- skeptical scientist
- closed-minded spiritualist
**Posts:**6142**Joined:**Tue Nov 28, 2006 6:09 am UTC**Location:**San Francisco

### Re: Cutting The Cake

My current best is somewhere around

I have an idea for a proof of maximality, but it's going to get really complicated and I don't really want to work it out.

**Spoiler:**

I have an idea for a proof of maximality, but it's going to get really complicated and I don't really want to work it out.

I'm looking forward to the day when the SNES emulator on my computer works by emulating the elementary particles in an actual, physical box with Nintendo stamped on the side.

"With math, all things are possible." —Rebecca Watson

"With math, all things are possible." —Rebecca Watson

- Cosmologicon
**Posts:**1806**Joined:**Sat Nov 25, 2006 9:47 am UTC**Location:**Cambridge MA USA-
**Contact:**

### Re: Cutting The Cake

Hmm, I'm pretty sure I can do better than that:But I'm still not sure I understand the rules, so I could be wrong.

**Spoiler:**

### Re: Cutting The Cake

Cosmologicon wrote:That's interesting, but I don't understand the rules, I think. It looks to me like most of your cuts on the right-hand diagram don't start and end at grid points.

Although it would appear that shifting the lines that don't meet a corner could certainly show the exact same solution. One would be lead to believe the OP was just sloppy when making his diagram.

~steve

### Re: Cutting The Cake

Cosmologicon wrote:That's interesting, but I don't understand the rules, I think. It looks to me like most of your cuts on the right-hand diagram don't start and end at grid points.

Although it would appear that shifting the lines that don't meet a corner could certainly show the exact same solution. One would be lead to believe the OP was just sloppy when making his diagram.

Very sloppy, I do apoligize. I was rushing and merely cut off the lines in order to make 4 pieces. I'll update it when I have the time.

For possible extra clarification, here's the only friend of mine who's replied yet's current best. 28. I've gotten higher, but not quite as many as you're getting! I'll test them out at some point... right now I really just want some sleep.

The original pieces are highlighted. Each line is straight and goes from one corner to the other, and the extra cuts create small pieces with 0.25 of the original cakelet, plus the two finger-like pieces, making 28 pieces in total.

This is, er, no offense but you are a robot, aren't you?

That's just, um, beautiful, beautiful beautiful... just beautiful.

One hot summer's night Lorraine said: "It's time for you to see the lighthouse"

Dr. Ivanovich, was it really necessary?

That's just, um, beautiful, beautiful beautiful... just beautiful.

One hot summer's night Lorraine said: "It's time for you to see the lighthouse"

Dr. Ivanovich, was it really necessary?

- Cosmologicon
**Posts:**1806**Joined:**Sat Nov 25, 2006 9:47 am UTC**Location:**Cambridge MA USA-
**Contact:**

### Re: Cutting The Cake

Well, here's my idea, although I'm lazy and I decided to do it on a 5x5 cake so you get the idea:

**Spoiler:**

There's 3 small pieces formed by the 3 red lines, and the 16 blue lines are all within the other (large) piece. The green line, which is the final cut, intersects each of the red and blue lines, and I guess it makes 20 new pieces, many of them very small. On the 12x12 cake, there would be 121 blue lines and the green line would make 125 new pieces. (I said 124 before; should be 125 I think.)

- skeptical scientist
- closed-minded spiritualist
**Posts:**6142**Joined:**Tue Nov 28, 2006 6:09 am UTC**Location:**San Francisco

### Re: Cutting The Cake

Cosmologicon wrote:Hmm, I'm pretty sure I can do better than that:But I'm still not sure I understand the rules, so I could be wrong.Spoiler:

I think you're making a fencepost error. If I'm picturing what you are saying correctly:

**Spoiler:**

Edit: You seem to have realized this yourself.

I'm looking forward to the day when the SNES emulator on my computer works by emulating the elementary particles in an actual, physical box with Nintendo stamped on the side.

"With math, all things are possible." —Rebecca Watson

"With math, all things are possible." —Rebecca Watson

### Re: Cutting The Cake

There is clearly an unspoken rule that the OP's friend is following and I'm wondering if the OP intended it or not. Is the following supposed to be part of the rules?

"All cuts must be part of the borders of the origonal four pieces"

"All cuts must be part of the borders of the origonal four pieces"

"Everything I need to know about parenting I learned from cooking. Don't be afraid to experiment, and eat your mistakes." - Cronos

- skeptical scientist
- closed-minded spiritualist
**Posts:**6142**Joined:**Tue Nov 28, 2006 6:09 am UTC**Location:**San Francisco

### Re: Cutting The Cake

BoomFrog wrote:There is clearly an unspoken rule that the OP's friend is following and I'm wondering if the OP intended it or not. Is the following supposed to be part of the rules?

"All cuts must be part of the borders of the origonal four pieces"

Except the friend isn't... However, he could have done more-or-less the same thing while following that.

I'm looking forward to the day when the SNES emulator on my computer works by emulating the elementary particles in an actual, physical box with Nintendo stamped on the side.

"With math, all things are possible." —Rebecca Watson

"With math, all things are possible." —Rebecca Watson

### Re: Cutting The Cake

My try:

**Spoiler:**

### Re: Cutting The Cake

33+1+3+80+7=124 Now With the new design i am just one pice short of the leading moddel...

Sorry fot the double post but i couldn't let it rest...

Also i don't want to be the guy that has to make all those cuts when everyone is hungry; without a laser at hand the knife will dissolve the poor cake in the prosses

Sorry fot the double post but i couldn't let it rest...

**Spoiler:**

Also i don't want to be the guy that has to make all those cuts when everyone is hungry; without a laser at hand the knife will dissolve the poor cake in the prosses

- skeptical scientist
- closed-minded spiritualist
**Posts:**6142**Joined:**Tue Nov 28, 2006 6:09 am UTC**Location:**San Francisco

### Re: Cutting The Cake

Moloch wrote:Spoiler:

**Spoiler:**

"With math, all things are possible." —Rebecca Watson

### Re: Cutting The Cake

skeptical scientist wrote:Spoiler:

**Spoiler:**

- parallax
**Posts:**157**Joined:**Wed Jan 31, 2007 5:06 pm UTC**Location:**The Emergency Intelligence Incinerator

### Re: Cutting The Cake

Consider all the intersection points of the cake. Consider the partition of these intersections such that two points are in the same partition if they are connected by a cut. Before cutting, there are 122 partition sets: one for all the boundary points, and one for each interior point. Consider making a new cut. If the cut connects two points in the same partition, then it forms a new piece. If it connects two points in different partitions, then the points in those partitions are now connected and form a new partition. Thus, each cut either forms a new piece or reduces the number of partitions by one. There can never be fewer than one partition. Thus, the greatest number of cuts you can make and leave the cake in four pieces is 121+3=124. At best, an additional cut will make one additional piece, plus one piece for each previous cut it intersects. Thus, the maximum number of pieces is 129.

In general, the total pieces after one additional cut can be at most (number of interior endpoints) + 2*(number of pieces prior).

In general, the total pieces after one additional cut can be at most (number of interior endpoints) + 2*(number of pieces prior).

Cake and grief counseling will be available at the conclusion of the test.

### Who is online

Users browsing this forum: No registered users and 9 guests