wu :: forums (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
riddles >> medium >> Cake Division
(Message started by: william wu on Jan 8th, 2003, 4:55pm)

Title: Cake Division
Post by william wu on Jan 8th, 2003, 4:55pm
Willywutang is holding a birthday party. Either p or q people are going to show up, where p and q are relatively prime numbers. Willy wants to cut the cake beforehand, so his guests don't waste time waiting for slices to be carved out. What is the smallest number of slices Willy must cut out such that every guest can be given the same amount of cake, regardless of whether p or q people show up? Why? (prove it) The slices do not have to be equally sized, and each guest could receive more than one slice. Also, the entire cake must be distributed amongst the guests -- there can be no leftovers.

Note: Two numbers are relatively prime if they share no common factors. So for example, the numbers 4 and 9 are relatively prime, but the numbers 10 and 15 are not because they share common factor 5.


Title: Re: Cake Division
Post by towr on Jan 9th, 2003, 12:25am
I think p+q -1
Just slice the cake in p pieces, then pretend it's still whole and slice it into q pieces. Only one cut can fall together with a prievious cut, since they're relative primes, so p+q-1 cuts means p+q-1 pieces..

It works for 2 and 3, 2 and 5, 3 and 4, 3 and 8.. So that's proove enough for me ;)

Title: Re: Cake Division
Post by towr on Jan 9th, 2003, 12:28am
Or just slice the cake in max(p,q) pieces, and Willy can eat the remaining |p-q| pieces himself if only min(p,q) people show up..

Title: Re: Cake Division
Post by James Fingas on Jan 9th, 2003, 10:33am
towr,

On that vein, he could just cut the cake into 1 piece and eat it all himself regardless of how many people show up. Mmmmm...

Title: Re: Cake Division
Post by towr on Jan 9th, 2003, 12:04pm
Well, you only live once.. But a whole cake is a bit much..

But the puzzle does state he wants to cut the cake.. Even though it doesn't specify he want to give people any cake (just everyone the same amount, which could be none).. But it being a birthday party the people would wait for the cake regardless of Willy's intention to give them any or none. And Willy doesn't want them to wait according to the riddle, so he then either has to give them cake, or tell them beforehand they won't get any (cake :p).

Title: Re: Cake Division
Post by James Fingas on Jan 9th, 2003, 12:41pm
You know what I think's a gyp? Willy is supplying the cake for his own birthday party!

Title: Re: Cake Division
Post by towr on Jan 9th, 2003, 12:57pm
Supplying your own cake is quite normal in many places.. Considering everyone else is bringing gifts..


actually, it's not specified it's his own birthday party..

Title: Re: Cake Division
Post by mike1102 on May 22nd, 2003, 9:37am
I think towr has the right idea but overlooked some things. Take the case where p=2, q=3. p=2 requires 1 cut that divides the cake into two equal slices. Likewise, q=3 requires two cuts that divide the cake into equal thirds - but none of the p=2 cuts are common with the q=3 cuts. Thus there will be p + q -2 cuts that produce p + q + 1 individual slices of cake. Willy makes p-1 parallel cuts, then rotates the cake 90deg and makes q-1 parallel cuts (the p cuts are perpendicular to the q cuts). Then, if p people arrive, distribute cake along th "p" axis or if q people arrive, distribute cake along the "q" axis and all guests will receive the same ammount of cake. So.... Willy makes p + q + 1 slices (pieces) of cake from p + q -2 cuts.

Title: Re: Cake Division
Post by towr on May 22nd, 2003, 11:36am

on 05/22/03 at 09:37:27, mike1102 wrote:
I think towr has the right idea but overlooked some things.
reconsidering everything, I think you've overlooked a round cake..
Which is the traditional birthday cake shape..

Title: Re: Cake Division
Post by Leonid Broukhis on May 22nd, 2003, 11:43am

on 05/22/03 at 11:36:03, towr wrote:
reconsidering everything, I think you've overlooked a round cake..
Which is the traditional birthday cake shape..

Reconsidering everything, including a round cake, I think you've overlooked the possibility of one of p or q being even, in which case the number of cuts will be much smaller. E.g. for {p, q} = {4, 3} the number of cuts is 4, for {8, 3} the number of cuts is 6, etc.


Title: Re: Cake Division
Post by towr on May 22nd, 2003, 12:18pm
Depends, I only considered cuts away from the center, and since the answer concerns the slices of cake you get that really doesn't make a difference..

Title: Re: Cake Division
Post by william wu on May 27th, 2003, 2:16pm
Edited the problem statement to specify that Willy wants to give the entire cake to the guests. Thanks to Geoff Canyon via e-mail for this good point.

Title: Re: Cake Division
Post by Papa Homer on May 28th, 2003, 1:50pm
Along the lines of towr's solution: cut the cake into p pieces in one dimension (slices) and into q pieces in another (layers).

Title: Re: Cake Division
Post by Nick on Jul 17th, 2003, 4:34pm
You know, usually the cake isn't cut until after the candles are blown out, so by then he should know how many people are there.  I don't see why Willy has to make things so complicated.



Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board