這是一道小學三年級上學期,數學廣角中關于搭配的題目。大意說,高個子舅舅春節回家,想給三個可愛的孩子小明、小強、小紅一些紅包用來買過年的玩具。他準備了6個紅包,每個里面10元錢。每個小朋友肯定能得到紅包,但不一定均分。問一共有幾種發的方法。

這道題目如果編程暴力窮舉的話會非常容易,但是如何用簡單直觀的方法讓小朋友明白卻并不簡單。其中一個方法是,為了保證每個小朋友都得到紅包,先每人發一個。

[1, 1, 1]

然后舅舅手里還剩三個紅包,每個紅包可以給三個小朋友,這樣3 x 3 x 3 = 27,共有27種發法。但是這27種中有很多重復的,例如先把第一紅包給小明,第二個給小紅,第三個再次給小明,結果是[2, 0, 1];但把第一個給小紅,后兩個給小明,雖然發放次序不同,可是結果仍然是[2, 0, 1]。

如果分別列出27種結果,然后去掉重復的(有超過一半都是重復的),這個過程對小朋友來說既容易出錯,也很繁瑣。

例如:

let expand = \(a, b, c) -> [(a+1, b, c), (a, b+1, c), (a, b, c+1)] in 
   concatMap expand $ concatMap expand $ concatMap expand [(1, 1, 1)]

列出所有27種結果,可以看到里面有多少種是重復的:

[(4,1,1),(3,2,1),(3,1,2),(3,2,1),(2,3,1),
(2,2,2),(3,1,2),(2,2,2),(2,1,3),(3,2,1),
(2,3,1),(2,2,2),(2,3,1),(1,4,1),(1,3,2),
(2,2,2),(1,3,2),(1,2,3),(3,1,2),(2,2,2),
(2,1,3),(2,2,2),(1,3,2),(1,2,3),(2,1,3),
(1,2,3),(1,1,4)]

有沒有更簡單點的辦法呢?先每人發一個紅包沒問題,為了排除重復情況,舅舅剩下的3個紅包不管怎么發,一共有3類不同的情況:

  1. 剩下的均分,每人再得一個,這樣只有一種結果[1, 1, 1] + [1, 1, 1] = [2, 2, 2];
  2. 剩下的都發給一個小朋友,這樣有三種結果:小明得到剩下的3個,或者小強,或者小紅;
  3. 一個小朋友得到剩下的兩個,一個得到剩下的1個。選得到兩個紅包的小朋友有3種,在此基礎上再從其余2個小朋友中選一個得到剩下的1個紅包。這樣共有3 x 2 = 6種。

綜合上述三種情況,共有1 + 3 + 6 = 10種分法。這個方法小朋友能夠理解,但是仍然有些麻煩。有沒有更加簡單優美的方法呢?

這時就要讓強大的同構思想上場了。我們先給小朋友們講另外一個故事。媽媽的三個女兒要出嫁了,她摘下了自己頸上的一串珍珠項鏈。上面有六顆又大又圓的珍珠:

o - o - o - o - o - o

媽媽拿起剪刀想把它拆成三段,分給三個女兒,有多少種分法呢?

6顆珍珠5段絲線,媽媽剪兩刀可以分成三段。第一刀有5種選擇,第二刀有4種選擇。如果第一刀剪在A位置,第二刀剪在B位置。那么如果讓時光倒流,前后反轉——第一刀剪在B位置,第二刀剪在A位置。得到的結果是一樣的。所以一共有 5 x 4 / 2 = 10種方法。

我們一下子就看出,分紅包問題和珍珠項鏈問題是同構的,紅包對應珍珠,三個小朋友對應三個女兒,媽媽對應舅舅,絲線剪刀對應紅包的分割。

下面是一個快速驗證(不是證明):

[(a, b, c) | a <- [1..4], b <- [1..4], c<-[1..4], a + b + c ==6]
[(1,1,4),(1,2,3),(1,3,2),(1,4,1),(2,1,3),(2,2,2),(2,3,1),(3,1,2),(3,2,1),(4,1,1)]

length [(a, b, c) | a <- [1..4], b <- [1..4], c<-[1..4], a + b + c ==6]
10

作為擴展,這里有一個思考題:如果可以允許有小朋友沒有得到紅包,有幾種分法?怎樣能得到優雅直觀的思路?

《同構——編程中的數學》中文版已可以從github上下載:https://github.com/liuxinyu95/unplugged