wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> medium >> Cake Division
        
(Message started by: GWabel on Jun 11^th, 2007, 1:53am)

Title: Cake Division
Post by GWabel on Jun 11^th, 2007, 1:53am

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.

Title: Re: Cake Division
Post by towr on Jun 11^th, 2007, 2:49am

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.

Title: Re: Cake Division
Post by Grimbal on Jun 11^th, 2007, 3:49am

I can think of 2 methods that both give [hide]p+q-1[/hide] parts.
but have no proof that either method is optimal.

Title: Re: Cake Division
Post by mc2 on Nov 6^th, 2007, 12:51pm

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

Title: Re: Cake Division
Post by towr on Nov 6^th, 2007, 1:17pm

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 :P
It didn't help that she needed to divide the strawberries on top as well.

Title: Re: Cake Division
Post by Joe Fendel on Nov 6^th, 2007, 1:36pm

on 06/11/07 at 03:49:23, Grimbal wrote:

I can think of 2 methods that both give [hide]p+q-1[/hide] parts.
but have no proof that either method is optimal.

Yes, that's what I get also. But I only have 1 method:

[hideb]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.[/hideb]

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

Title: Re: Cake Division
Post by Joe Fendel on Nov 6^th, 2007, 4:36pm

Ah, of course - the other method is actually more natural. Leave it to me to find the tricky one first!

[hideb]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.[/hideb]

These two methods produce different results for p=4, q=3:
[hideb]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).[/hideb]

Were these Grimbal's two methods? :-/

Title: Re: Cake Division
Post by towr on Nov 7^th, 2007, 1:23am

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.

Title: Re: Cake Division
Post by pex on Nov 7^th, 2007, 3:37am

on 11/07/07 at 01:23:21, 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. ???

Title: Re: Cake Division
Post by towr on Nov 7^th, 2007, 4:09am

on 11/07/07 at 03:37:49, 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..

Title: Re: Cake Division
Post by Joe Fendel on Nov 7^th, 2007, 2:07pm

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.

[hideb]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.[/hideb]

Title: Re: Cake Division
Post by Grimbal on Nov 8^th, 2007, 1:38am

Proof of optimality approved! :)

Title: Re: Cake Division
Post by Joe Fendel on Nov 8^th, 2007, 8:29am

Grimbal and I have each found two methods to get [hide]p+q-1[/hide] 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?

Title: Re: Cake Division
Post by Aryabhatta on Nov 8^th, 2007, 9:14am

Nice proof Joe!