9
$\begingroup$

You are expecting guests to your birthday party. You know that there will be at most 8 guests, but you don't know how many will actually come. What is the smallest number of pieces you should divide your cake into, so that no matter how many guests come, everyone (including yourself) can be given an equal share? Note that the whole cake must be used and individuals can have more than one part of the cake.

Here is a similar puzzle: Nine gangsters and a gold bar

Good luck!

Improve this question
$\endgroup$
9
  • $\begingroup$ Is it required to distribute the whole cake? Or is keeping out some cake allowed? $\endgroup$ – Zoir Sep 23 '19 at 3:37
  • 1
    $\begingroup$ The whole cake must be used. Although I think the problem is just as hard. If you are keeping one of the pieces then that is an extra piece and you still need to distribute the remaining pieces (equivalent problem). $\endgroup$ – Dmitry Kamenetsky Sep 23 '19 at 3:43
  • 3
    $\begingroup$ @Randal'Thor It is not just the LCM. That gives an upper bound on the number of pieces required, but it is a real puzzle to bring that number down to the fewest with which you can still make the required fractions. Take a look at the linked question for example.. $\endgroup$ – Jaap Scherphuis Sep 23 '19 at 9:51
  • 2
    $\begingroup$ My apologies, I did misunderstand the question. Voted to reopen now. $\endgroup$ – Rand al'Thor Sep 23 '19 at 17:46
  • 1
    $\begingroup$ @Norbert yes they can have more than one part, I'll add it to the text $\endgroup$ – Dmitry Kamenetsky Sep 23 '19 at 22:56
11
$\begingroup$

The cheeky answer is:

$1$

The reasoning is:

You asked:
".. everyone (including yourself) can be given an equal share?"
In this case we just give everyone an equal share of no cake.

For a not so cheeky answer there is an upper bound of

$25$ pieces

We arrive at this by

Splitting the cake first into $2520$ pieces (the LCM) and then greedily combining pieces together so that the cake can still be divided.

I implemented this algorithm here and golfed it here.

An inductive proof will show that the greedy algorithm will not improve if we subdivide further to any multiple of $2520$.
Spoiler blocks are difficult to work with so I will not put the proof here, but roughly if we start with $2520\times n$ then at every step the size of each partition will be divisible by $n$. Thus we will get the same partitions as with $2520$, just scaled up by a factor of $n$.

The pieces I came up with are:

[1,1,2,3,3,7,8,21,35,35,35,35,39,39,80,80,136,140,196,224,280,280,280,280,280]
Where a piece of size 1 is $1/2520$th of the cake.

The groupings themselves can be found as the output of the program. I am not savy enough with markdown to get them to cooperate with spoiler blocks.

There is a lower bound of

$17$ pieces

A proof of this:

Let us say that we have a way which involves only $16$ pieces.

The first thing we can say is that there must be at least two pieces of size $1/9$. Due to the fact that if we divide $16$ pieces amoung $9$ people there must be two people who only get one piece. To keep things equal those pieces must each be $1/9$ of the cake.

The next thing we can say is that when dividing amoung $8$ people each person must get two pieces. If at least one person were to get less than two pieces then there would be at least one piece of size $1/8$. If there were a piece size $1/8$ we could not divide evenly amoung $9$ people. And if someone were to get more than two pieces, then someone else would have to get less than two via the pigeon hole principle.

If we combine these two facts we find that there are also two pieces of size $1/72$. Since when we divide amoung $8$ people each person gets two pieces and there are two pieces of size $1/9$, two people must get a piece of size $1/9$ and another piece that adds with $1/9$ to get $1/8$ (one person cannot get both pieces of size $1/9$ since $2/9 > 1/8$). $1/8 - 1/9$ is $1/72$.

Now following similar logic to our second point we can see that when dividing amoung $7$ people, $6$ people must get $2$ pieces and one person must get $3$ pieces.

Now when dividing amoung $7$ people there are two scenarios we will look at:
Scenario 1:
The two pieces of size $1/72$ go to two different people. Since only one person gets three pieces, one of the two people with a $1/72$ must have exactly two pieces of cake.
This makes there other piece size $1/7-1/72=65/504$. Now it might not be super clear, but there is a problem with this. That piece $65/504$ is bigger than $1/9$ of the cake. Meaning that when we try to distribute amoung $9$ people someone is going to get more than their share.
So this scenario is not possible leaving us with scenario 2.
Scenario 2:
In this scenario one person gets both of the pieces of size $1/72$. Since $2/72$ ($1/36$) is far less than $1/7$ this person must be the person with $3$ pieces. Furthermore there last piece must be of size $29/252$. And again we have a problem, $29/252$ is larger than $1/9$ ($1/9$ is $28/252$). So this scenario is impossible to.

Now since there is no way to divide our $16$ pieces amoung $7$ people that does not reach a contradiction we know that there is no way $16$ pieces can satisfy our request.

Improve this answer
$\endgroup$
10
  • 1
    $\begingroup$ Take a look at the linked question. What you have calculated is an upper bound, but it can be done with far fewer pieces. (Note - the question has been edited to use 6 instead of 9, making it easier to do by hand). $\endgroup$ – Jaap Scherphuis Sep 23 '19 at 9:53
  • $\begingroup$ I have returned it back to 9, so this answer is still valid. $\endgroup$ – Dmitry Kamenetsky Sep 23 '19 at 10:13
  • 1
    $\begingroup$ @JaapScherphuis Ok, I have reduced the number of pieces used greatly. However it is still only an upper bound. $\endgroup$ – Sriotchilism O'Zaic Sep 23 '19 at 18:07
  • 2
    $\begingroup$ I like how you golfed your code even though you're not on CGSE. $\endgroup$ – xnor Sep 25 '19 at 3:02
  • 1
    $\begingroup$ I suspect your solution is optimal, though I don't know see how to prove it. Here's another way to arrive at the same count. Make a cut at every 1/5 mark (1/5, 2/5, 3/5, 4/5). Do the same for the 1/7, 1/8, and 1/9 marks. This gets you all the pieces of those fractions and their divisors. The only question then is 1/6's, but that works out from the 1/8's and 1/9's. $\endgroup$ – xnor Sep 25 '19 at 3:15
2
$\begingroup$

This is probably not the minimum, but it is an improvement to the answer from @Sriotchilism O'Zaic:

$23$ pieces

with the sizes

1,1,1,6,14,15,29,34,70,80,90,109,120,125,150,155,160,190,200,210,235,245,280

In 9 parts:

{280} {245,34,1} {235,29,14,1,1} {210,70} {200,80} {190,90} {160,120} {155,125} {150,109,15,6}

In 8 parts:

{280,34,1} {245,70} {235,80} {210,90,14,1} {200,109,6} {190,125} {160,155} {150,120,29,15,1}

In 7 parts:

{280,80} {245,109,6} {235,125} {210,150} {200,160} {190,120,34,14,1,1} {155,90,70,29,15,1}

In 6 parts:

{280,125,14,1} {245,160,15} {235,109,70,6} {210,120,90} {200,155,34,29,1,1} {190,150,80}

In 5 parts:

{280,125,70,29} {245,150,109} {235,155,90,15,6,1,1,1} {210,160,120,14} {200,190,80,34}

I used the $18$ pieces from the linked puzzle as my starting point and

could extend this to cover $6$ parts by adding just $1$ piece. But to extend it to cover $5$ parts took an additional $4$ extra pieces.

Improve this answer
$\endgroup$
0
$\begingroup$

An attempt: Let us call $a$ the number of parts the cake will be divided into.

$a$ must be divisible by $ 2, 3, 4, 5, 6, 7, 8\,$and$\,9$.

The above set of divisors can be reduced to $5, 7, 2^{3}$ and $9$.

So $a$ must be of the form $$a=k\times 5\times7\times8\times 9$$

where $k$ is a natural number. What is the value of $k$ for which $a$ is minimum? Obviously, $1$.

Thus the cake must be divided into $2520$ parts.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ That's an upper bound. See the answer in linked puzzle. $\endgroup$ – Dmitry Kamenetsky Sep 24 '19 at 22:30
-2
$\begingroup$

The problem might be similar to this problem: Given a multiset M of rational numbers where the sum of M equals 1, this is "n-distributable" for an n n∈N, if there exists a partition M1⊔...⊔Mn of M, that the sum of each subset Xi equals 1/n. We would like to find for a fixed k (k∈N) the minimal possible cardinality of a (a1,a2,..,ak) distributable multiset. There are some existing references that in case k=9, n=

19

but I do not have proof (nor do the reference works), we will have to work on it.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Can you explain why you think this answer is correct? Answers without explanation are usually deleted. $\endgroup$ – Deusovi♦ Oct 16 '19 at 22:51
  • $\begingroup$ @Deusovi OP had an explanation but edited it out. I rolled back to the previous edit so that the explanation would be visible $\endgroup$ – HTM Oct 16 '19 at 23:01
  • $\begingroup$ If this counts as explanation, it is my intuition. But this I have already written down, so I am not sure why I have to repeat myself $\endgroup$ – balazs.com Oct 16 '19 at 23:01
  • $\begingroup$ The problem is that there is no explanation that is why I deleted this answer considering it not useful.:) $\endgroup$ – balazs.com Oct 16 '19 at 23:05
  • $\begingroup$ @balazs.com Can you elaborate on what you mean by that? I believe your first answer was perfectly fine (though you may want to elaborate a bit more on the problem you mention) and is at least better than just saying it's intuitive without going any further $\endgroup$ – HTM Oct 16 '19 at 23:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.