均分蛋糕.doc

均分蛋糕
一次晚餐会可能有p人或者q人参加。,才能使p人或者q人出席的任何一种情形,都能平均将蛋糕分食。

解法1 最少应将蛋糕切成p+q-1块。不妨设蛋糕是长方形的。我们首先用平行于一对边的p-1条平行线,将蛋糕划成p等份;再用同一方向的另外q-1条平行线,将蛋糕划成q等份。然后沿所画的+=p +q-2条线切割,将蛋糕切成p+q-1块。这样的切割办法显然符合要求。
将证明块数p+q-1不能再减小。为此,我们构造一个有p+q个顶点的图。其中的p个顶点表示第一情形的p位来客,另q个顶点表示第二情形的q位来客。约定用图的边表示蛋糕的切块。每条边所连接的两个顶点分别为两种情形取食该块的客人。根据题目要求,对于两种来客情形,所有的切块分别被划成等分量的p堆,或者等分量的q堆,为客人所分食。在所构造的图中任意两个顶点之间必有链相连。否则,将有顶点的一个连通分支不与其他顶点相连。设该连通分支含有第一情形顶点a个和第二情形顶点b个。显然a,b。连通分支所含的这一部分蛋糕在两种来客情形分别能划成a个蛋糕份额和b个蛋糕份额。因此

其中,a,b,但这与p和q互质的条件相矛盾。
最后,我们指出:有p+q个顶点的连通图至少有p+q-1条边。因此块数p+q-1是不能减少的。

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

我们断言:将蛋糕切成p+q-1块是必要的和充分的。下面,对辗转相除法的算式数目进行归纳,以证明所断言的命题。
如果n=1,那么p=1。显然将蛋糕切成q块是必要而且充分的。此时自然有p+q-1=q。现在,假定在来客数分别为r2和p的前提下,将蛋糕切成
r2+p-1
块是必要而且充分的。
回到来客分别为p和q的情形。首先将蛋糕切出k1p块,每块的份额是整个蛋糕的。然后,将占蛋糕总量的剩余部分切分,使得有p位来客的第一种情形可将剩余蛋糕分成p等份,有q位来客的第二种情形可将剩余蛋糕分成r2等份。根据归纳假设,只需将剩余蛋糕切成
r2+p-1
块即可。于是,对于整个蛋糕而言,适合要求的切块总数为
k1p+r2+p-1=q+p-1
还需证明此数是必须的。考察既可被p位客人等量
取食又可被q位客人等量取食的任意一种切分蛋糕办法。不妨设蛋糕总量为pq个单位。将任一种适合要求的切分方式用一个p×q矩阵[aij]表示。其中
aij∈{0,1,2,…,p}
非0的aij就是蛋糕的一个切块的单位数。矩阵[aij]的非0元