Pizza War 3

There is a formula for this type of question: to divide $M$ (continuously divisible) items evenly amongst $N$ groups requires that the $M$ items be divided, as a whole, into a minimum of $M + N - gcd(M,N)$ pieces.

In this case we have $M = 484, N = 576,$ giving an answer of

$484 + 576 - gcd(484,576) = 1060 - gcd(2^{2}11^{2}, 2^{6}3^{2}) = 1060 - 2^{2} = \boxed{1056}.$

The proof of this formula requires a bit of graph theory. Suppose we have a bipartite graph with disjoint sets of $M$ and $N$ vertices, in this case representing the number pizzas and persons, respectively. The number of pieces then corresponds to the number of edges in the graph. Each of the $N$ persons gets a total of $\frac{M}{N} = \frac{A}{B}$ pizzas, where the fraction on the right is in reduced form, i.e., $M = A*gcd(M,N)$ and $N = B*gcd(M,N)$ .

Now each (self-contained) component, ("tree"), of the graph represents a complete dissolution of an integer number of pizzas amongst an integer number of persons and thus involves a minimum of $A$ pizzas and $B$ persons. Our graph will then have at most $gcd(M,N)$ components, and thus at least $M + N - gcd(M,N)$ edges, or pieces. So this is the theoretical minimum; the next question is whether this minimum is achievable.

The answer is: yes, this minimum can be achieved. If we were to imagine the pizzas being lined up in a row, and then each person in turn being given $\frac{A}{B}$ pizzas by making whatever cuts necessary to the pizzas as we move along the row, then after $B$ persons have been served we will have used up $A$ pizzas. This sequence is then repeated $gcd(M,N)$ times, in essence creating a bipartite graph of this many components and thus $M + N - gcd(M,N)$ edges, or pieces. So the theoretical minimum is achievable.