一、问题
新年走亲戚。你手笔很大，今年的压岁钱就发金锞子了。取了一斤金子，准备叫人熔成金锞子。
亲戚家有n个小孩，本来呢，做n个1/n斤的金锞子就行了。可是另一个有m个小孩的亲戚说不定那天也会去。厚此薄彼不好，他家的小孩要是在场也得发一样的。但反正总共只有一斤金子，如果是这样，就一人发1/(n+m)斤金子。
那这金锞子怎么个做法呢？令n+m=k，你可以做nk个1/(nk)斤的。如果到时候有n个小孩，就一人发k个；如果有k个小孩，就一人发n个。
但你希望做的金锞子的数目尽可能地少。
比如在n=2，m=1（则k=3）时，你不必做2*3=6个1/6斤的金锞子，而是只要做4个：2个1/3斤的，2个1/6斤的。碰上只有2个小孩，就每人拿一个1/3斤的，一个1/6斤的；要是3个小孩，则2个人每人拿一个1/3斤的，最后那个拿两个1/6斤的。
又比如n=4, m=3（则k=7）时，你不必做4*7=28个1/28斤的金锞子，而是可以做16个：4个1/7斤的，12个1/28斤的。如果到时有4个小孩，每人1个1/7的，3个1/28的；7个小孩的话，则4人每人拿个1/7的，另3人每人拿4个1/28的。但这并非最少的金锞子数量，其实你可以只做10个：4个1/7的，2个1/14的，2个1/28的，2个3/28的，具体怎么凑就先不说了。
二、一般方案
对于任何正整数n和m，令k=n+m，可用以下简单的方法，让所需制作的金锞子数成为n+k-g，其中g是n和k的最大公约数：
先把金子弄成均匀细长条，令其长度为1，然后在1/n、2/n、……、(n-1)/n处切开（切口n-1个）。类似地，也在1/k、2/k、……、(k-1)/k处切开（切口k-1个）。切完后将分开的每块熔成一个金锞子即可。到亲戚家后，分起来也很容易，有n个小孩的话按前面一种切法来，有k个小孩按后面的切法来。
如果n和k互素（也即g=1），那么这(n-1)+(k-1)刀就都切在不同处，将细长条切成了n+k-1块。如果n和k不互素，这(n-1)+(k-1)刀中就会有g-1刀切在同一个地方，其中只有(n-1)+(k-1)-(g-1)刀是不同的，切成的块数是n+k-g。
所以n=2,m=1时，要做2+3-1=4个金锞子；n=4，m=3时，要做4+7-1=10个金锞子；而n=4,m=6时，则要做4+10-2=12个。
但n+k-g个是不是最少的？是的，有兴趣的朋友可以试试能不能找到比较简单的方法来证明。我在下一篇则会介绍一种基于简单的图论知识的证法。
（待续）
网友评论