Author |
Topic: Cake Division (Read 995 times) |
|
GWabel
Newbie
Gender: 
Posts: 1
|
 |
Cake Division
« on: Jun 11th, 2007, 1:53am » |
 Quote  Modify
|
So, I'm not quite sure how to approach this one. Most of my friends have suggested some function of p + q, but the proviso that the slices don't have to be equally sized just throws me completely off, and I'm wondering if a constant answer is possible.
Sorry if there's already been a discussion regarding this particular riddle, and thanks in advance.
|
|
 IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Cake Division
« Reply #1 on: Jun 11th, 2007, 2:49am » |
Quote Modify
|
Well, the answer will necessarily have to depend in some way on p and q. So a constant answer isn't an option (unless you give them all nothing).
A typical solution is to divide the cake in equal pieces of size 1/(p*q), using p*q cuts. Then if p people show up, they each get q of those pieces; if q people show up, they each get p of those pieces.
But you can immagine that for even reasonable p and q, you'll end up with mashed cake.
Luckily you can do better, by not using equally sized pieces of cake.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Cake Division
« Reply #2 on: Jun 11th, 2007, 3:49am » |
Quote Modify
|
I can think of 2 methods that both give p+q-1 parts.
but have no proof that either method is optimal.
|
|
IP Logged |
|
|
|
mc2
Newbie
Gender:
Posts: 5
|
|
Re: Cake Division
« Reply #3 on: Nov 6th, 2007, 12:51pm » |
Quote Modify
|
No frosting.
Slice one is horizontal transverse at mid height.
Then conventionally slice for four equal and get eight.
Have large amounts of the trash can punch with the cake.
campi,
mc2
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Cake Division
« Reply #4 on: Nov 6th, 2007, 1:17pm » |
Quote Modify
|
I think you're thinking of a different cake division puzzle than the poster of this thread.
In this one, you have to cut the cake in pieces such that you can either divide it among p people or q people (with p and q relatively prime, if I recall correctly). *
The one you seem to be thinking of is cutting a cake in 8 using three cuts.
*) In an anime I watched a few weeks ago this actually sort of came up. Except more and more people came in that needed a piece of cake, so it had to be cut up further and further. At the end the girl doing the cutting (who was extremely anal about cutting precisely equal parts) broke down and put the cake in the blender 
It didn't help that she needed to divide the strawberries on top as well.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Joe Fendel
Full Member
Posts: 158
|
|
Re: Cake Division
« Reply #5 on: Nov 6th, 2007, 1:36pm » |
Quote Modify
|
on Jun 11th, 2007, 3:49am, Grimbal wrote:I can think of 2 methods that both give p+q-1 parts.
but have no proof that either method is optimal. |
|
Yes, that's what I get also. But I only have 1 method:
| hidden: | | Assume p > q. Begin by cutting the cake into p equal slices (of size 1/p) with p cuts. Then set q of these aside, and divide the remaining (p-q) slices (considered as one large clump) into q "slices" of size (p-q)/pq with q-1 cuts (though some of these new "slices" may in fact be in 2 parts). Now if p people arrive, serve the p slices as they were originally cut. If q people arrive, everybody gets one of the q slices of size (1/p) (which we set aside) plus 1-2 additional smaler slices of total size (p-q)/pq. We've had p+q-1 cuts, and therefore there must be p+q-1 total slices. |
What is the other method to do this? And like Grimbal, I have no general proof of optimality, though for q=1 or 2 it is pretty clearly optimal (and unique - i.e. Grimbal's "other method" must end up with the same slice sizes).
|
|
IP Logged |
|
|
|
Joe Fendel
Full Member
Posts: 158
|
|
Re: Cake Division
« Reply #6 on: Nov 6th, 2007, 4:36pm » |
Quote Modify
|
Ah, of course - the other method is actually more natural. Leave it to me to find the tricky one first!
| hidden: | | Make 1 cut, C. Then make (p-1) cuts around in a circle to cut p slices of size 1/p, but don't remove these slices. Next, again using C as an initial cut, make (q-1) cuts around in a circle to cut q slices of size 1/q. This is a total of 1+(p-1)+(q-1) = p+q-1 cuts. |
These two methods produce different results for p=4, q=3:
| hidden: | My first method makes slices of size (1/4), (1/4), (1/4), (1/12), (1/12), (1/12).
My second method makes slices of size (1/4), (1/4), (1/6), (1/6), (1/12), (1/12). |
Were these Grimbal's two methods? 
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Cake Division
« Reply #7 on: Nov 7th, 2007, 1:23am » |
Quote Modify
|
Do we need to cut wedges? Otherwise p+q-2 is fairly trivial (well, conceptually; actually doing it is harder)
Come to think of it, you might still make wedges, but they wouldn't meet at the center of the cake.
|
| « Last Edit: Nov 7th, 2007, 4:08am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
pex
Uberpuzzler
Gender:
Posts: 880
|
|
Re: Cake Division
« Reply #8 on: Nov 7th, 2007, 3:37am » |
Quote Modify
|
on Nov 7th, 2007, 1:23am, towr wrote:| ... p+q-2 is fairly trivial ... |
|
I don't get this. Do you mean you can do p=2, q=3 in three parts? Those three parts would have to be of size 1/3 and there is no way we can make halves with that. 
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Cake Division
« Reply #9 on: Nov 7th, 2007, 4:09am » |
Quote Modify
|
on Nov 7th, 2007, 3:37am, pex wrote:| I don't get this. Do you mean you can do p=2, q=3 in three parts? Those three parts would have to be of size 1/3 and there is no way we can make halves with that. |
|
Err.. I'm confusing the number of cuts with the number of pieces it seems..
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Joe Fendel
Full Member
Posts: 158
|
|
Re: Cake Division
« Reply #10 on: Nov 7th, 2007, 2:07pm » |
Quote Modify
|
I've found a proof of optimality, though it's a bit ghoulish.
We're going to poison these slices of cake one at a time.
| hidden: | Let's imagine that we have found a way to slice our cake into N slices such that they can be distributed to either p people or q people in a way that gives everyone an equal share.
Consider the p guests in the one case and q guests in the other as distinct "potential guests," and let's assume that we have our mapping from the slices to each collection (i.e. for each slice, there are exactly 2 potential guests who can eat that slice, one from the p group and one from the q group).
We then poison a slice of cake. This creates 2 potential victims, one from each group. I claim that we can proceed to poison all N-1 additional slices in such a way that each additional slice adds no more than 1 potential victim.
Suppose not. Then each victim of the p group must have their entire cake allotment poisoned (otherwise we could poison a slice without adding to the victims in the p group, and adding at most one victim in the q group). Thus the total amount of cake poisoned is a multiple of 1/p. Similarly it is a multiple of 1/q. But since p and q are relatively prime, we must have the entire cake poisoned, and there are then no more slices.
By proceeding thus we have created no more than 2+(N-1) potential victims. Yet this includes all p+q potential guests, since now the entire cake is poisoned. Thus we have p+q <= 2+N-1, so N must be at least p+q-1. |
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Cake Division
« Reply #11 on: Nov 8th, 2007, 1:38am » |
Quote Modify
|
Proof of optimality approved! 
|
|
IP Logged |
|
|
|
Joe Fendel
Full Member
Posts: 158
|
|
Re: Cake Division
« Reply #12 on: Nov 8th, 2007, 8:29am » |
Quote Modify
|
Grimbal and I have each found two methods to get p+q-1 slices, which we now know is optimal.
A harder question: Find all possible ways to slice the cake into this minimal number of slices such that it satisfies the conditions of the problem. As I mentioned earlier, if we assume p > q, then for q=1 or 2, there is only 1 way. For q=3, things get interesting. When p=1 (mod 3), then there are 2 ways, but when p=2 (mod 3), there is only 1 way. What is the general answer?
|
|
IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: Cake Division
« Reply #13 on: Nov 8th, 2007, 9:14am » |
Quote Modify
|
Nice proof Joe!
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print