11
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ A nontrivial example would add motivation.. $\endgroup$ – Brendan McKay Aug 10 '15 at 22:52
  • $\begingroup$ @Brendan, non-triviality is in the eye of the beholder, but there are some examples at the second math.stackexchange link. In particular, I sketch an argument that $(3,4,n)$, for $\gcd(n,6)=1$, can be done $M=n+4$, and I give a couple of other examples. My $(3,4,n)$ is based on the $(3,4,5)$ example at the first math.stackexchange link. $\endgroup$ – Gerry Myerson Aug 11 '15 at 0:10
  • $\begingroup$ @Gerry: Thanks. It seems we are seeking a vertex of a polytope that has the greatest number of zero components. Investigating the polytope combinatorially might be productive. $\endgroup$ – Brendan McKay Aug 11 '15 at 1:04
  • 1
    $\begingroup$ @Dennis : Consider the case $(3,4)$ for illustration. Any solution has the form of a $3\times 4$ matrix of nonnegative rational (might as well be real) numbers with row sums $1/3$ and column sums $1/4$. Such matrices form a convex polytope defined by the row/column sums and the nonnegativity. The problem is to minimise the number of nonnegative entries, i.e. to maximise the number of zero entries. I think (is it obvious?) that this maximum occurs at some vertex of the polytope but I don't know how to find that vertex. $\endgroup$ – Brendan McKay Aug 12 '15 at 1:44
  • 1
    $\begingroup$ See also oeis.org/A265286 $\endgroup$ – Gerry Myerson Feb 13 '18 at 23:31
3
$\begingroup$

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]

$\endgroup$
  • $\begingroup$ Not original, but worth repeating: not minimal, but you can get a good start with S - m cuts where S is the sum of the set of numbers, and m the number of members. (Maybe could be tweaked for multisets). Cut 1 into the largest number a_1 of pieces, and then stack all but a_2 of these pieces and make a_2 - 1 cuts of this stack, and the stack them on the a_2 pieces. Now stack all but a_3 of these equal stacks and divide this tall stack into a_3 equal sized pieces. This should give a good stat on the optimization. Gerhard "Start Simply, End With Frosting" Paseman, 2015.12.04 $\endgroup$ – Gerhard Paseman Dec 5 '15 at 5:37
  • $\begingroup$ On multiplying everything by 30 to get whole numbers, the 11-part $(4,5,6)$ solution above is $[1,1,2,2,4,5,7,8,10,10,10]$. Another 11-part solution is given by $[1,2,3,4,5,5,6,7,8,9,10]$. $\endgroup$ – Gerry Myerson Feb 13 '18 at 3:03
2
$\begingroup$

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)$.

$\endgroup$

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.