Suppose we have a finite amount of numbers $x_1, x_2, ..., x_n$ ($x_i\in\mathbb{N}$) and an object that should be divided into parts in such a way that it can be without further dividing distributed in $x_i$ equal piles for any $1\leq i\leq n$.

The question is what is the minimal amount of parts for some $x_1, x_2, ..., x_n$ that would allow us to do that?

Example: we have a cake and expect some friends, but we don't know for sure how many of them are coming. But somehow we know, that the total amount of people will be either 5 or 6 $(x_1 = 5, x_2 = 6)$. So we divide a cake beforehand into $5\times 6 = 30$ parts, and so in each scenario we can just give the guest his share of the cake.

Optimization. Of course, 30 parts is too many. In the example above we could just divide the cake into 5 parts, then ignore it and divide the cake (like it was whole) into 6 parts. First we do 4 cuts, second we do 5 cuts; they don't coincide because 5 and 6 are coprimes. Total 9 cuts gives us 10 pieces. So instead of cutting the cake in 30 pieces, we can only cut it in 10. And that is the minimum here.

Simple case. Let $x_1$ and $x_2$ be two coprime numbers. Then, using the same argumentation as above with the case $x_1=5, x_2=6$, we can note that the minimal amount of parts is $(x_1-1)+(x_2-1)+1$ which is equal to $x_1+x_2-1$.

Generalization. First I thought that for $n$ coprime numbers the solution is simple and beautiful: $$ \sum_{i=1}^n (x_i-1) + 1 $$ But this formula is wrong for $n>2$ as shows the following counterexample.

Counterexample. For $x_1=3, x_2 = 4, x_3 = 5$ the formula gives the answer 10. But that's not the minimum, as we can divide at least in nine portions: $$ \frac{1}{60} + \frac{2}{60} + \frac{4}{60} + \frac{5}{60} + \frac{7}{60} + \frac{8}{60} + \frac{10}{60} + \frac{11}{60} + \frac{12}{60} = 1 $$ so we can split it equally in 3 pieces: $$ \left(\frac{1}{60} + \frac{2}{60} + \frac{7}{60} + \frac{10}{60}\right) + \left(\frac{4}{60} + \frac{5}{60} +\frac{11}{60}\right) + \left(\frac{8}{60} + \frac{12}{60}\right) = 1 $$ in 4 pieces: $$ \left(\frac{1}{60} + \frac{2}{60} + \frac{12}{60} \right) + \left(\frac{4}{60} +\frac{11}{60}\right) + \left(\frac{5}{60} + \frac{10}{60}\right) + \left(\frac{7}{60} + \frac{8}{60}\right) = 1 $$ in 5 pieces: $$ \frac{12}{60}+\left(\frac{1}{60} + \frac{11}{60} \right) + \left(\frac{2}{60} +\frac{10}{60}\right) + \left(\frac{4}{60} + \frac{8}{60}\right) + \left(\frac{5}{60} + \frac{7}{60}\right) = 1 $$

To sum up, the posed question has an evident answer in the case $n=1,2$, but in the case $n=3$ (and higher) I didn't discover any pattern.

[Edit] Related Topics:

Minimum Cake Cutting for a Party



  • 1
    $\begingroup$ How did you discover this counterexample? $\endgroup$ – rywit Aug 1 '15 at 12:35
  • 1
    $\begingroup$ Also, in your example with 5 and 6 people you say you make 4 cuts and then separately 5 cuts for a total of 9. But you could align the first cut in each set. So you could make 4 cuts (for 5 people) and then 4 more cuts (reusing one of the existing cuts) for 6 people. Thus a total of only 8 cuts is required in this case. Am I right? $\endgroup$ – rywit Aug 2 '15 at 12:50
  • $\begingroup$ When you write, in the "simple case", that the answer "seems to be" $x_1+x_2-1$, do you mean you can prove it's at least that big? or do you mean you can prove it's at least that small? or what? $\endgroup$ – Gerry Myerson Aug 2 '15 at 12:51
  • $\begingroup$ @rywit, I think we're trying to minimize the number of pieces, rather than the number of physical cuts. $\endgroup$ – Gerry Myerson Aug 2 '15 at 12:52
  • $\begingroup$ @GerryMyerson Ah, you're right. Thanks! $\endgroup$ – rywit Aug 2 '15 at 14:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.