Cutting The Cake

A forum for good logic/math puzzles.

Moderators: jestingrabbit, Moderators General, Prelates

User avatar
Sruixan
Posts: 89
Joined: Sat Jan 10, 2009 5:40 pm UTC
Location: seaside or spires

Cutting The Cake

Postby Sruixan » Sat Jan 10, 2009 6:00 pm UTC

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...

Image
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?

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

Re: Cutting The Cake

Postby Cosmologicon » Sat Jan 10, 2009 6:20 pm UTC

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.

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

Re: Cutting The Cake

Postby skeptical scientist » Sat Jan 10, 2009 6:27 pm UTC

My current best is somewhere around
Spoiler:
86. I haven't bothered counting carefully.

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

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

Re: Cutting The Cake

Postby Cosmologicon » Sat Jan 10, 2009 6:37 pm UTC

Hmm, I'm pretty sure I can do better than that:
Spoiler:
124.

It involves making 121 cuts that don't create any pieces (11 cuts from each of 11 points along the bottom) and then 3 more to make 4 pieces. The final cut crosses each of these lines, making one more piece for each it crosses.
But I'm still not sure I understand the rules, so I could be wrong.

User avatar
Dromtry
Posts: 169
Joined: Mon Jul 07, 2008 8:22 pm UTC
Location: The Ninjas Are Coming, NH

Re: Cutting The Cake

Postby Dromtry » Sat Jan 10, 2009 6:46 pm UTC

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

User avatar
Sruixan
Posts: 89
Joined: Sat Jan 10, 2009 5:40 pm UTC
Location: seaside or spires

Re: Cutting The Cake

Postby Sruixan » Sat Jan 10, 2009 9:54 pm UTC

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.

Image

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?

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

Re: Cutting The Cake

Postby Cosmologicon » Sat Jan 10, 2009 10:21 pm UTC

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:
cake-5x5.png
cake-5x5.png (1.58 KiB) Viewed 3513 times
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.)

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

Re: Cutting The Cake

Postby skeptical scientist » Sat Jan 10, 2009 10:27 pm UTC

Cosmologicon wrote:Hmm, I'm pretty sure I can do better than that:
Spoiler:
124.

It involves making 121 cuts that don't create any pieces (11 cuts from each of 11 points along the bottom) and then 3 more to make 4 pieces. The final cut crosses each of these lines, making one more piece for each it crosses.
But I'm still not sure I understand the rules, so I could be wrong.

I think you're making a fencepost error. If I'm picturing what you are saying correctly:
Spoiler:
You start out with 4 pieces, and then your next cut crosses 124 nearly vertical lines for an extra 125 pieces, for a total of 129.

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

User avatar
BoomFrog
Posts: 1070
Joined: Mon Jan 15, 2007 5:59 am UTC
Location: Seattle

Re: Cutting The Cake

Postby BoomFrog » Mon Jan 12, 2009 8:49 am UTC

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"
"Everything I need to know about parenting I learned from cooking. Don't be afraid to experiment, and eat your mistakes." - Cronos

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

Re: Cutting The Cake

Postby skeptical scientist » Mon Jan 12, 2009 8:58 am UTC

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

User avatar
Moloch
Posts: 85
Joined: Fri Jan 16, 2009 1:30 pm UTC
Location: Germany

Re: Cutting The Cake

Postby Moloch » Sun Jan 18, 2009 8:44 pm UTC

My try:
Spoiler:
Image
Image

I guess the new pices are 1+2+33+66+1=103 BUT i might have missed someof those sneaky little bastards. I havn't beaten the current leading design but at least i drew mine and noticed all the problems with corners that arise in the design. Perhaps There is some more potential in this setup and someone else will discover it ;)

Edit: found one more so 104 :)
Edit2: I see i corrected myself in a place that wasnt wrong so on the right side there can be one more line that reaches the right wall, adding another 11 lines, getting me with 115 pices nearly back into the race oO

User avatar
Moloch
Posts: 85
Joined: Fri Jan 16, 2009 1:30 pm UTC
Location: Germany

Re: Cutting The Cake

Postby Moloch » Sun Jan 18, 2009 9:14 pm UTC

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...
Spoiler:
Added the purple lines instead of the correction nr.2 i made in my previous setup. the result is two more pices for each line

Image
Image

I would be pleased if anyone finds the last pice that my solution lacks to the 125 from Cosmologicon :)


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

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

Re: Cutting The Cake

Postby skeptical scientist » Sun Jan 18, 2009 10:05 pm UTC

Moloch wrote:
Spoiler:
I would be pleased if anyone finds the last pice that my solution lacks to the 125 from Cosmologicon :)

Spoiler:
Your red vertical line doesn't follow the rules. However, this is easily fixed, giving you the same number of pieces. If you want, you can rearrange everything to have your red vertical line pass through any of the columns, with virtually no change to the number of pieces cut. However, because you can't use all the possible lines on the top row, you pick up a few more pieces by moving it to the right and adding a few more cuts to the top row. In fact, if you move it all the way to the right, your solution basically becomes the same as Cosmologicon's.
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

User avatar
Moloch
Posts: 85
Joined: Fri Jan 16, 2009 1:30 pm UTC
Location: Germany

Re: Cutting The Cake

Postby Moloch » Sun Jan 18, 2009 11:40 pm UTC

skeptical scientist wrote:
Spoiler:
Your red vertical line doesn't follow the rules. However, this is easily fixed, giving you the same number of pieces. If you want, you can rearrange everything to have your red vertical line pass through any of the columns, with virtually no change to the number of pieces cut. However, because you can't use all the possible lines on the top row, you pick up a few more pieces by moving it to the right and adding a few more cuts to the top row. In fact, if you move it all the way to the right, your solution basically becomes the same as Cosmologicon's.


Spoiler:
Your right about the rules even though it dosn't change much; correction is upper end of the red line half a box to the left and lower end of the line half a box to the right.
With the purple line included my solution has the advantage over Cosmologicons by creating 12 pices in each horizontal row compared to 11 in his design BUT his design works better with the top and bottom row. In those places my design looses many pices, Cosmlogicons just looses some in his first row and gets the whole of the last row. There has to be a solution that utilizes both high number of pices/row and optimal use of every row...

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

Re: Cutting The Cake

Postby parallax » Tue Jan 20, 2009 4:02 am UTC

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).
Cake and grief counseling will be available at the conclusion of the test.


Return to “Logic Puzzles”

Who is online

Users browsing this forum: No registered users and 9 guests