Saudi Arabian IMO Booklet

We claim that the answer is $m+n-\gcd (m,n)$. Firstly, note that if we consider the cake as the interval $[0,1]$ and make cuts at points with coordinates $\frac{k}{m}$ ($0<k<m$) and $\frac{l}{n}$ ($0<l<n$), then we will be able to satisfy the condition of the problem. Moreover, there will be $m-1$ cuts with $\frac{k}{m}$, $n-1$ cuts with $\frac{l}{n}$, $\gcd (m,n)-1$ of which coincide. Therefore we will have $$m+n-\gcd (m,n)-1$$ cuts, so $m+n-\gcd (m,n)$ parts. Let us show that this estimate is sharp. For that purpose, consider a bipartite graph, with the vertices of one side corresponding to the $m$ persons on the party, and the vertices of the other side corresponding to the $n$ persons on the party. We connect the vertices $v$ and $u$ by an edge, corresponding to the piece of cake, if the piece of cake will be given to the person $v$, if exactly $m$ persons attend, and to the person $u$, if exactly $n$ persons attend. Consider a component of connectivity of the graph. Then, if it contains $m_1$ edges in one side and $n_1$ edges in the other side, then the edges of it correspond to a cake with weight $\frac{m_1}{m}=\frac{n_1}{n}$. Therefore, $m_1\ge \frac{m}{\gcd (m,n)}$. Thus, the number of components of connectivity is at most $\gcd (m,n)$. The graph has $m+n$ vertices and at most $\gcd (m,n)$ components of connectivity, so the number of edges is at least $m+n-\gcd (m,n)$ (the equality is obtained, when each of the components is a tree). $\square$