Minimum Cake Cutting for a Party

You are organizing a party. However, the number of guests to attend your party can be anything from $a_1$, $a_2$, $\ldots$, $a_n$, where the $a_i$'s are positive integers. You want to be prepared, so you want to cut a cake into smaller pieces. The pieces are not necessarily of equal size. The requirement is that, no matter how many guests come (which you will have known before distributing the cake), you will be able to give each of them some pieces of the cake without having to cut the cake any further so that everybody will get the same amount of cake. What is the minimum number of pieces of your cake you will have to cut it into?

Trivially, if $n=1$, then the answer is $a_1$. The answer is also known for $n=2$, which is $a_1+a_2-\gcd\left(a_1,a_2\right)$ (if you wonder why graph theory is in the tag, it is because the only proof known to me for the $n=2$ case is done via a graph-theorical argument). I conjecture that the answer, in general, is $$m:=\sum_{j=1}^n\,(-1)^{j-1}\,g_j\,,$$ where $$g_j:=\sum_{1\leq k_1<k_2<\ldots<k_j\leq n}\,\gcd\left(a_{k_1},a_{k_2},\ldots,a_{k_j}\right)$$ for $j=1,2,\ldots,n$ (here, $g_1$ is simply $a_1+a_2+\ldots+a_n$). It is easy to cut the cake into $m$ pieces to satisfy the required condition.

Apparently, the conjecture is false for $n>2$ (see Dividing the whole into a minimal amount of parts to equally distribute it between different groups.). However, I expect that my guess is not far away from the correct answer.

EDIT: The $n=2$ case with $\gcd\left(a_1,a_2\right)=1$ appeared as a problem for the Spring Contest, A Level, of the Tournament of the Towns of 1990. See https://keoserey.files.wordpress.com/2012/12/imtot-book-3.pdf (page 35 of the PDF).

Related Topics:

Dividing the whole into a minimal amount of parts to equally distribute it between different groups.

https://puzzling.stackexchange.com/questions/19870/nine-gangsters-and-a-gold-bar/19881#19881

https://mathoverflow.net/questions/214477/minimal-possible-cardinality-of-a-a-1-a-k-distributable-multiset

Solution 1:

Here is a sketch of the proof that if $\gcd(n,6)=1$ then you can satisfy $3$, $4$, or $n$ guests with $n+4$ pieces.

We imagine the cake to be of size $12n$. We cut it into $n-4$ pieces, each of size $12$, and what's left over gets cut into eight pieces, of sizes $1,2,4,5,7,8,10,11$, making $n+4$ pieces all told, as promised.

Now we can certainly share the cake equally among $n$ guests: $n-4$ of them get a single piece of size $12$, and each of the other four guests get $11+1$, or $10+2$, or $8+4$, or $7+5$.

If we have four guests, we want to split the cake into four portions, each of size $3n$. If we distribute the $n-4$ size $12$ pieces among our four guests as evenly as possible, we will either have three guests with $3n-9$, and one guest with $3n-21$, or we will have three guests with $3n-15$ and one guest with $3n-3$. [Of course, this assertion requires checking, but it really is a simple matter of considering the cases $n=4k+1$ and $n=4k+3$, and doing the arithmetic.] In the first case, we make up the deficit with $8+1$, $7+2$, $5+4$, and $11+10$. In the second case, with $11+4$, $10+5$, $8+7$, and $2+1$.

Finally, if we have three guests, we want to split the cake into three portions, each of size $4n$. Again, distribute the $n-4$ size $12$ pieces as evenly as possible. We wind up with three guests at $4n-16$, or else with two guests at $4n-20$ and one guest at $4n-8$ [and again I leave it to you to check the arithmetic here]. In the first case, we bring all the guests up to $4n$ by distributing $11+5$, $10+4+2$, and $8+7+1$. In the second case, $11+5+4$, $10+8+2$, $7+1$.

EDIT: I think more generally if $3<a<b$ are pairwise coprime, then you can keep $3$, $a$, or $b$ guests happy with $a+b$ pieces. I won't try to write a proof, just present an example with $a\ne4$.

For $3,5,7$, let the cake have size $3\times5\times7=105$. Split the cake in seven pieces of size $15$, then split five of those pieces into $1$ and $14$, $2$ and $13$, $4$ and $11$, $5$ and $10$, $7$ and $8$ (that's all the possible splits, avoiding only those not prime to $3$). All told, $5+7=12$ pieces.

Sharing among seven guests is obvious.

Sharing among five guests is accomplished by $15+5+1$, $15+4+2$, $14+7$, $13+8$, $11+10$.

Sharing among three guests is accomplished by $15+15+5$, $14+13+8$, $11+10+7+4+2+1$.

We can also do $4,5,7$ in twelve pieces, using two $20$s and each odd number from $1$ to $19$, inclusive.

Solution 2:

This is a proof for the case where $n=2$, as requested by vonbrand.

Consider a bipartite graph graph $G\left(V_1\cup V_2,E\right)$, where $V_1$ and $V_2$ are bipartite sets with $\left|V_1\right|=a_1$ and $\left|V_2\right|=a_2$ such that they represent the guests who may attend the party and $\left\{v_1,v_2\right\}$ with $v_1 \in V_1$ and $v_2\in V_2$ are in the edge set $E$ if and only if there exists a piece of this cake that will be given to $v_1$ if $a_1$ guests come such that this same piece will be given to $v_2$ if $a_2$ guests come. Clearly, we need at least $|E|$ pieces of cake. We shall verify that $|E|\geq a_1+a_2-d$, where $d:=\gcd\left(a_1,a_2\right)$. It suffices to show that there are at most $d$ connected components in $G$.

Suppose that $C$ is a connected component of $G$. Write $C_1$ for the set of vertices of $C$ in $V_1$ and $C_2$ for the set of vertices of $C$ in $V_2$. Each guest in $V_1$ takes $\frac{1}{a_1}$ amount of cake, while each guest in $V_2$ takes $\frac{1}{a_2}$ amount of cake. Hence, the total amount of cake given to guests in $C_1$ is $\frac{\left|C_1\right|}{a_1}$, while the total amount of cake given to guests in $C_2$ is $\frac{\left|C_2\right|}{a_2}$. Since $C$ is a connected component, guests in $C_1$ must consume the same amount of cake as that consumed by guests in $C_2$; otherwise, there will be an edge going from $C_1$ or $C_2$ to a vertex outside $C$. Ergo, we must have that $$\frac{\left|C_1\right|}{a_1}=\frac{\left|C_2\right|}{a_2}\text{ or }\frac{a_2}{d}\left|C_1\right|=\frac{a_1}{d}\left|C_2\right|\,.$$ Hence, $\frac{a_1}{d}$ divides $\left|C_1\right|$, as $\gcd\left(\frac{a_1}{d},\frac{a_2}{d}\right)=1$. Thence, $\left|C_1\right| \geq \frac{a_1}{d}$ (and similarly, $\left|C_2\right| \geq \frac{a_2}{d}$).

Consequently, every connected component of $G$ has at least $\frac{a_1}{d}$ vertices in $V_1$. Hence, $G$ can have at most $d$ connected components. The proof is now complete.

P.S. You can probably see why this sort of arguments won't work for $n>2$. If we try to create $n$-partite graphs in the same way, then the number of pieces of cake is related to the number of $n$-cliques of this graph. However, not all $n$-cliques can be assigned to a piece of cake, and two distinct pieces of cake can produce two non-identical, but non-disjoint, $n$-cliques. Hence, for $n>2$, I think we need a completely new way to solve the problem. We might be able to use $n$-uniform hypergraphs in tackling the case $n>2$.