Author |
Topic: Cake Division (Read 893 times) |
|
william wu
wu::riddles Administrator
Gender: 
Posts: 1291
|
 |
Cake Division
« on: Jan 8th, 2003, 4:55pm » |
 Quote  Modify
|
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.
|
| « Last Edit: May 27th, 2003, 2:17pm by william wu » |
 IP Logged |
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Cake Division
« Reply #1 on: Jan 9th, 2003, 12:25am » |
Quote Modify
|
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 
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Cake Division
« Reply #2 on: Jan 9th, 2003, 12:28am » |
Quote Modify
|
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..
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: Cake Division
« Reply #3 on: Jan 9th, 2003, 10:33am » |
Quote Modify
|
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...
|
|
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Cake Division
« Reply #4 on: Jan 9th, 2003, 12:04pm » |
Quote Modify
|
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).
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: Cake Division
« Reply #5 on: Jan 9th, 2003, 12:41pm » |
Quote Modify
|
You know what I think's a gyp? Willy is supplying the cake for his own birthday party!
|
|
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Cake Division
« Reply #6 on: Jan 9th, 2003, 12:57pm » |
Quote Modify
|
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..
|
| « Last Edit: Jan 9th, 2003, 12:59pm by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
mike1102
Guest
|
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.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Cake Division
« Reply #8 on: May 22nd, 2003, 11:36am » |
Quote Modify
|
on May 22nd, 2003, 9:37am, 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..
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Leo Broukhis
Senior Riddler
Gender:
Posts: 459
|
|
Re: Cake Division
« Reply #9 on: May 22nd, 2003, 11:43am » |
Quote Modify
|
on May 22nd, 2003, 11:36am, 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.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Cake Division
« Reply #10 on: May 22nd, 2003, 12:18pm » |
Quote Modify
|
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..
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
william wu
wu::riddles Administrator
Gender:
Posts: 1291
|
|
Re: Cake Division
« Reply #11 on: May 27th, 2003, 2:16pm » |
Quote Modify
|
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.
|
|
IP Logged |
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
|
|
|
Papa Homer
Guest
|
Along the lines of towr's solution: cut the cake into p pieces in one dimension (slices) and into q pieces in another (layers).
|
|
IP Logged |
|
|
|
Nick
Guest
|
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.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print
Remove