一次晚餐会可能有p人或者q人参加（p和q是给定的互质的整数）。这次晚餐会准备了一个大蛋糕.问最少要将这蛋糕分成多少块（每块大小不一定相等），才能使p人或者q人出席的任何一种情形，都能平均将蛋糕分食。

　　解法1 最少应将蛋糕切成p+q－1块。不妨设蛋糕是长方形的。我们首先用平行于一对边的p－1条平行线，将蛋糕划成p等份；再用同一方向的另外q－1条平行线，将蛋糕划成q等份。然后沿所画的（p－1）+（q－1）=p +q－2条线切割，将蛋糕切成p+q－1块。这样的切割办法显然符合要求。

　　将证明块数p+q－1不能再减小。为此，我们构造一个有p+q个顶点的图。其中的p个顶点表示第一情形的p位来客，另q个顶点表示第二情形的q位来客。约定用图的边表示蛋糕的切块。每条边所连接的两个顶点分别为两种情形取食该块的客人。根据题目要求，对于两种来客情形，所有的切块分别被划成等分量的p堆，或者等分量的q堆，为客人所分食。在所构造的图中任意两个顶点之间必有链相连。否则，将有顶点的一个连通分支不与其他顶点相连。设该连通分支含有第一情形顶点a个和第二情形顶点b个。显然a<p，b<q。连通分支所含的这一部分蛋糕在两种来客情形分别能划成a个蛋糕份额和b个蛋糕份额。因此

　　其中，a<p，b<q，但这与p和q互质的条件相矛盾。

　　最后，我们指出：有p+q个顶点的连通图至少有p+q－1条边。因此块数p+q－1是不能减少的。　　

　　解法2 不妨设p≤q。因为p与q互质，所以用辗转相除法（Euclid算法）。最后求得的最大公约数应该是1。　　　　

　　我们断言：将蛋糕切成p+q－1块是必要的和充分的。下面，对辗转相除法的算式数目进行归纳，以证明所断言的命题。

　　如果n=1，那么p=1。显然将蛋糕切成q块是必要而且充分的。此时自然有p+q－1=q。现在，假定在来客数分别为r₂和p的前提下，将蛋糕切成

r₂+p－1

块是必要而且充分的。

　　回到来客分别为p和q的情形。首先将蛋糕切出k₁p块，每块的份额是整个蛋糕的。然后，将占蛋糕总量 的剩余部分切分，使得有p位来客的第一种情形可将剩余蛋糕分成p等份，有q位来客的第二种情形可将剩余蛋糕分成r₂等份。根据归纳假设，只需将剩余蛋糕切成

r₂+p－1

块即可。于是，对于整个蛋糕而言，适合要求的切块总数为

k₁p+r₂+p－1=q+p－1

　　还需证明此数是必须的。考察既可被p位客人等量取食又可被q位客人等量取食的任意一种切分蛋糕办法。不妨设蛋糕总量为pq个单位。将任一种适合要求的切分方式用一个p×q矩阵[a_ij]表示。其中

a_ij∈{0，1，2，…，p}　　

　　非0的a_ij就是蛋糕的一个切块的单位数。矩阵[a_ij]的非0元质数数目就是蛋糕的切块数。如果到达的客人是p位，那么就依次取第1行，第2行，……，第p行中非0数所表示的那些切块；如果到达的客人是q位，那么就依次取第1列，第2列，……，第q列中非0数所表示那些切块。因此，每行的元素和等于q，每列的元素和等于p。每一行至多有k₁个元素等于p。假定每行都恰有k₁个元素等于p，则可按照前面讨论中的办法去做。根据归纳假设，蛋糕的剩余部分至少必须切成r₂+p－1块，总共切块数不少于p+q－1块。现在设某一行等于p的元质数目少于k₁，不妨设是第i行，则该行至少有两个非0元素小于p，设为a_ij和a_ik。因为第j列元素之和等于p，所以该列至少还有另一个非0元素a_hj。我们分别将a_ij，a_ik，a_hj，a_hk更换成a_ij+1，a_ik－1，a_hj－1，a_hk+1，则矩阵元素的行和与列和都不改变，不会有小于0或大于p的元素出现，并且大于0的元质数不会增加。经过有限次这样的操作，必能使a_ij变成p。于是任意切分总可以化归到这样一种形式：其矩阵表示的每一行都恰有k₁个元素等于p。于是，可以引用前面的讨论结果，最后完成证明。