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!
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 size1is $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.
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.
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.
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.
