这是一道小学三年级上学期,数学广角中关于搭配的题目。大意说,高个子舅舅春节回家,想给三个可爱的孩子小明、小强、小红一些红包用来买过年的玩具。他准备了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