cutting bread problem

Question

Here's the question:
If we have m loaves of bread and want to divide them between n people equally what is the minimum number of cuts we should make?
example:
3 loaves of bread and 15 people the answer is 12 cuts.
6 loaves of bread and 10 people the answer is 8 cuts.

for example 1, I found that I should cut each piece of bread 4 times so that we can have 15 pieces in total, but I can't find an algorithm for it. Any help would be appreciated.

Answer 1

If $k$ is the number of breads and $n$ is the number of people, you can always do it with $n - \gcd(n,k)$ cuts. Just treat all the breads as one long bread. This would need $n-1$ cuts. But then you can save all the cuts that are already there, i.e. where the different breads separate, which results in $\gcd(n,k) - 1$ saved cuts. Thus we need at most $n - \gcd(n,k)$ cuts.

Answer 2

For the first you want to give each person $\frac 15$ of a loaf. If the loaf is linear you need $4$ cuts to make $5$ pieces.

For the second you want to give each person $\frac 6{10}=\frac 35$ of a loaf. You cut $\frac 35$ off the first loaf and give it to the first person. You give the remaining $\frac 25$ to the second person and cut $\frac 15$ off the second loaf to complete their share. The next $\frac 35$ of the second loaf goes to the third. The last $\frac 15$ and the first $\frac 25$ of the third loaf go to the fourth, leaving $\frac 35$ for the fifth. Repeat on the remaining three loaves.

Note that this assumes the loaves can only be cut crosswise. If you have a round loaf you can get fourths with only two cuts, not three.