金錁子難題（上）——壓歲錢咋給得這麼難

來源安安以遷遷

一、問題

新年走親戚。你手筆很大，今年的壓歲錢就發金錁子了。取了一斤金子，準備叫人熔成金錁子。

親戚家有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個是不是最少的？是的，有興趣的朋友可以試試能不能找到比較簡單的方法來證明。我在下一篇則會介紹一種基於簡單的圖論知識的證法。

（待續）

來源：安安以遷遷

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！