Minimal possible cardinality of a $(a_1, ..., a_k)$-distributable multiset

Question

Suppose we have a multiset $M$ of positive rational numbers. Sum of $M$ equals $1$. We'll call this multiset $n$-distributable for some $n\in \mathbb{N}$, if there exists a partition $M_1 \sqcup ... \sqcup M_n$ of the $M$ such that the sum of each (multi)subset $X_i$ equals $\frac{1}{n}$. If the multiset is $n$-distributable and $m$-distributable for some $n,m\in\mathbb{N}$, we will call it $(n,m)$-distributable, and so on.

The problem is to find for some fixed $a_1, \ldots, a_k \in \mathbb{N}$ the minimal possible cardinality of a $(a_1, ..., a_k)$-distributable multiset.

Real-world analogy. You are organizing a party. You know that the number of guests to attend your party can be anything from $a_1, \ldots, a_k \in \mathbb{N}$. In order to be prepared you cut the cake beforehand into smaller pieces, not necessarily of equal size. The requirement is that, no matter how many guests come, 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?

The question. Formulated like this, is it a solved problem? If it's not, what specific cases are discussed and where could we read about it? If it is solved, well... basically the same, what mathematical branch is it and where to read about it? I tried to ask it on MSE here: https://math.stackexchange.com/questions/1381042/dividing-the-whole-into-a-minimal-amount-of-parts-to-equally-distribute-it-betwe. After that some other gentleman asked essentially the same question: https://math.stackexchange.com/questions/1383406/minimum-cake-cutting-for-a-party. The latter even has a bounty which is running out, but noone seems to know the answer (or maybe we chose wrong tags). I tried to dig into this problem by myself, but being an amateur, all I wind up with is a lot of specific made up terminology, some useless properties, couple of toy model cases solved and a constant feeling that I'm trying to invent a bicycle. Any insight would be greatly appreciated.

Answer 1

Here is a Mixed Integer Linear Problem (MILP) formulation that may be solved in practice for some instances with MILP-solvers like CPLEX.

For every integer vector $(i_1,\dots,i_k)\in [1,a_1]\times\cdots\times[1,a_k]$, let us introduce two variables: a nonnegative real (rational) $x_{i_1,\dots,i_k}$ and a binary $y_{i_1,\dots,i_k}$.

The $x$'s represent the elements of $M$ (with some elements being zero -- the more such elements, the better). They satisfy the following equalities: $$\forall j\in[1,k]\quad\forall t\in[1,a_j]\ :\qquad\sum_{i_1,\dots,i_k\atop i_j=t} x_{i_1,\dots,i_k} = \frac{1}{a_j}.$$

In an optimal solution, we want as many as possible $x$'s be zero and this is why we need $y$'s. In an optimal solution, they will represent indicator values for the positivity of $x$'s, i.e., $y_{i_1,\dots,i_k}=1$ iff $x_{i_1,\dots,i_k}>0$. This can be achieved with the inequalities: $$x_{i_1,\dots,i_k} \leq y_{i_1,\dots,i_k}$$ and the objective function: $$\min \sum_{i_1,\dots,i_k} y_{i_1,\dots,i_k}.$$

I have implemented this in Sage (with CPLEX) and here is a couple of examples of computed optimal $M$'s:

(3,4,5): [1/60, 1/30, 1/20, 1/12, 7/60, 2/15, 1/6, 1/5, 1/5]

(4,5,6): [1/60, 1/60, 1/30, 1/30, 1/15, 1/12, 7/60, 2/15, 1/6, 1/6, 1/6]

UPDATE. Here is another MILP formulation, which can be used to test whether a particular value $m=|M|$ is achievable. In this approach, we typically have smaller number of variables (equal $m+2\cdot m\cdot (a_1+\dots+a_k)$), and there is no objective function, so we look only for a feasible solution.

First, we introduce $m$ variables $M_1,\dots,M_m$ standing for the elements of $M$.

Then for each $i\in [1,m]$, $j\in [1,k]$, $t\in [1,a_j]$, we introduce a real variable $x_{i,j,t}$ and a binary variable $y_{i,j,t}$, for which we want $x_{i,j,t}=M_i$ and $y_{i,j,t}=1$ iff in the partition of $M$ into $a_j$ parts $M_i$ contributes to the $t$-th part; otherwise $x_{i,j,t}=y_{i,j,t}=0$. We achieve this with the following constraints: $$\begin{cases} x_{i,j,t}\leq y_{i,j,t},\\ \sum_{t=1}^{a_j} x_{i,j,t} = M_i,\\ \sum_{t=1}^{a_j} y_{i,j,t} = 1, \\ \sum_{i=1}^m x_{i,j,t} = \frac{1}{a_j}. \end{cases} $$

For example, for $(a_1,a_2,a_3,a_4)=(4,5,6,7)$ and $m=14$, my implementation of this approach obtains the following elements of $M$:

[1/210, 1/140, 3/140, 1/42, 13/420, 23/420, 9/140, 11/140, 37/420, 41/420, 47/420, 19/140, 29/210, 1/7]

Answer 2

Too long for a comment.

For $k=2$ the answer is $a_1+a_2-\mathrm{gcd}(a_1,a_2)$, this is well known. The text below is essentially a duplicate of math.stackexchange.com/a/1388683/87355 and other existed proof.

The example is to take a circular cake, inscribe a regular $a_1$-gon and a regular $a_2$-gon which have $\mathrm{gcd}(a_1,a_2)$ common vertices, and use for sector partitions.

The estimate may be done as follows: if the first party is for $a_1$ women and the second for $a_2$ men, draw the edge between, say, Ann and Bob if they share a virtual piece of cake. If a connected component contains $b_1$ women and $b_2$ men, we get $b_1/a_1=b_2/a_2$ by a double counting of the cake. That yields $b_1\geqslant a_1/\mathrm{gcd}(a_1,a_2)$ and the total number of components does not exceed $\mathrm{gcd}(a_1,a_2)$. Thus the number of edges is not less than $a_1+a_2-\mathrm{gcd}(a_1,a_2)$.