Sharing a pie evenly among an unknown number of people. [duplicate]

Question

This is a question inspired by the question "Nine gangsters and a gold bar" on the Puzzling Stack Exchange.

Suppose you're throwing a party, and you know that either 7, 8, or 9 people will arrive. Before anyone arrives, you want to cut the pie into the fewest number of pieces such that you can give everyone an equal amount.

In this case, you can cut the pie into 18 pieces of the following sizes (this is conjectured to be the minimal number of pieces).

$$\frac{1}{168}, \frac{1}{72}, \frac{1}{56}, \frac{1}{36}, \frac{2}{63}, \frac{1}{28}, \frac{23}{504}, \frac{1}{21}, \frac{25}{504}, \frac{5}{84}, \frac{31}{504}, \frac{4}{63}, \frac{19}{252}, \frac{5}{63}, \frac{1}{12}, \frac{47}{504}, \frac{7}{72}, \frac{1}{9}$$

Then you can divide this into nine parts:

$$ \left(\frac{1}{168}, \frac{23}{504}, \frac{5}{84}\right), \left(\frac{1}{72}, \frac{7}{72}\right), \left(\frac{1}{56}, \frac{47}{504}\right), \left(\frac{1}{36}, \frac{1}{12}\right), \left(\frac{2}{63}, \frac{5}{63}\right), \left(\frac{1}{28}, \frac{19}{252}\right), \left(\frac{1}{21}, \frac{4}{63}\right), \left(\frac{25}{504}, \frac{31}{504}\right), \text{ and } \left(\frac{1}{9}\right). $$

Into eight parts: $$ \left(\frac{1}{168}, \frac{1}{28}, \frac{1}{12}\right), \left(\frac{1}{72}, \frac{1}{9}\right), \left(\frac{1}{56}, \frac{1}{21}, \frac{5}{84}\right), \left(\frac{1}{36}, \frac{7}{72}\right), \left(\frac{2}{63}, \frac{47}{504}\right), \left(\frac{23}{504}, \frac{5}{63}\right), \left(\frac{25}{504}, \frac{19}{252}\right), \text{ and } \left(\frac{31}{504}, \frac{4}{63}\right) $$

And into seven parts: $$ \left(\frac{1}{168}, \frac{1}{72}, \frac{1}{21}, \frac{19}{252}\right), \left(\frac{1}{56}, \frac{1}{36}, \frac{1}{28}, \frac{31}{504}\right), \left(\frac{2}{63}, \frac{1}{9}\right), \left(\frac{23}{504}, \frac{7}{72}\right), \left(\frac{25}{504}, \frac{47}{504}\right), \left(\frac{5}{84}, \frac{1}{12}\right), \text{ and } \left(\frac{4}{63}, \frac{5}{63}\right) $$

---

The question

I'm interested in an algorithm that can produce such a minimal pie cut. In this case, it would take in the set of the possible numbers of guests, $\{7,8,9\}$, and output the list of fractions above—or a different list of minimal length.

I don't particularly care about the computational complexity of the program.

I am interested in proving that the program outputs the minimal number of "slices".

---

More examples

$$ \begin{align*} f(\{2\}) = f(\{1,2\}) &= \left(\frac{1}{2},\frac{1}{2}\right) \\ f(\{n\}) = f(\{1,n\}) &= \underbrace{\left(\frac{1}{n},\frac{1}{n},\cdots,\frac{1}{n}\right)}_n \\ f(\{2,3\}) &= \left(\frac{1}{3},\frac{1}{3},\frac{1}{6},\frac{1}{6}\right) \end{align*} $$

Answer 1

There is an obvious solution that is of course extremely slow. Since you said you are not interested in the complexity, this should not be a problem.

So first of all, there is a clear upper estimation for the number of fractions. Let $k_1, \ldots, k_r$ be the possible numbers of guests, and let $N$ be the least common multiple of these numbers. Then you can solve the problem with $N$ fractions, cutting the pie into N equal slices.

Introduce $N$ variables $x_1, \ldots, x_N$. Produce all partitions of these variables into $k_1, \ldots, k_r$ subsets. A variation of such partitions consists of a partition into $k_1$ subsets, ..., a partition into $k_r$ subsets.

Produce a system of linear equations as follows: given the partition into $k_1$ subsets, for each such subset, write the equation that the sum of variables in that subset is $1/k_1$. Same for all other $k_i$.

Finally, introduce the constraints that all the $x_i$ are non-negative.

Solve with simplex method. If you find a solution for any of the variations of partitions, then you decrease $N$, and repeat. I guess this last part could be done more cleverly (somehow looking deeper into the simplex method and find a solution with as many zeros as possible?), but again, you are only interested in a theoretically correct algorithm, so there you go.

Sorry if this was not helpful. Just tell me, and then I delete the answer.