中学数学建模方法实战：揪出泄密三人帮

美国纽约大学库兰特研究院的计算机科学系教授丹尼斯·夏沙，主要从事谜题的设计及破解，最近他出版了《艾科博士的网络谜题：给骇客与数学侦探的36道谜题》一书（w.w.Norton，2002），其中一道谜题为：某政府首长让九位顾问参赞机密，结果他发现，当他透露某些消息给这些顾问后，机密竟然就上了隔天的报纸.报纸编辑只愿意刊登有三人以上共同证实的消息，另外，首长相当确定，泄密的人一定恰有三个人.为了找到泄密三人帮，这位首长决定：每天透露一份消息给四位顾问，如果消息走漏了，他再对这可疑的四位顾问，一次透露消息给其中三人知道.他有两个目标：第一，最多只能走漏两次消息，一次在四人组合，另一次顶多是在三人组合时；第二，他希望能找出一系列恰当的四人组合，保证他能找到可疑的四人组合，进而找到其中泄密的三人帮，而且他还希望提供消息的次数不超过25次.试用数学建模的方法解决这位首长的问题[5].

【问题分析】

原始问题的关键是想找出一系列的四人组合，而一个四人组合包含4个三人组合，再最多提供3次消息就可从四人组合中找出泄密的三人帮.我们知道九个人的三人组合共有组，一个四人组合包含4个三人组合.因此，我们首先想到从九个人中找出21个四人组合来包含所有不同的三人组合，问题即可解决.但是实际上找不到这样的21个四人组合，运行如下MATLAB程序可获得含有互不重复三人组合的所有四人组，共14组.

主程序：

函数f1.m:

所以试图一次就找出题目要求的一系列四人组合的办法是行不通的.我们用穷举法得知，包含八个人的56()个不同的三人组合的四人组合最少有14个.于是想到先把某一位顾问隔离出去，对剩余的八位顾问的14个四人组合发布消息.若消息有泄密，则泄密三人帮包含在八个人中；若14组都没有泄密，则被隔离的那个人一定是泄密者.再采用类似的方法可判断出另外两个泄密者.

【符号设定】

为了叙述方便，设九位顾问的编号为1，2，3，…，9号.

【模型建立及求解】

为了从9个人中找出3个泄密者，最多需要经过三个步骤，且每个步骤都有相应的命题作为理论依据，在每个步骤中都给出了具体的操作方法.

步骤1　考察9个人中任一被选定的人（例如“9号”，这无损一般性，下同）是否为泄密者？在得出否定结论时，通过本步骤可找到3个泄密者；在得出肯定结论时，为了找到另外两个泄密者，需进入下一个步骤.

命题1　在8个人的四人组合中，存在14个四人组合，恰好包含这8个人所有不同的三人组合（这样的14个四人组合并不唯一）.

证明　如果存在这样的四人组合，则其个数k1=14.事实上，若k1≠14，则由于每一个四人组合包含4个三人组合，因此，这k1个四人组合所包含的三人组合的个数为4k1≠56，但是，8个人的三人组合恰有56个，故k1=14.

要完成命题1的证明，还要至少给出一种方法来寻找这14个四人组合.14个四人组合要包含56个三人组合，则任两个四人组合所包含的三人组合各不相同.不妨以除“9号”之外的8个人为例，把8个人两两分为4组（例如12，34，56，78），我们给出如下的方法：

（1）从这4组中任选两组，共有种选法.

（2）从这4组中每组各选一个元素.事实上，若选了三个组中的三个元素，要使所选四人组没有3个人相同，对另一组的两个元素只能有一种取法.因此有种选法.

通过（1），（2）两步，可找出14个四人组合来包含全部的三人组合，并给出至少一种这样的14个四人组合为：

证毕.

操作1　对命题1证明中给出的某一种14个四人组合，按任意顺序提供消息.

情形1-1　若某个四人组合使消息走漏，则3个泄密者就在这个四人组合中，这个四人组合包含4个三人组合，任意选出其中3个三人组合，再提供消息（最多3次），如果某个三人组合使消息走漏，便找到了三个泄密者；如果选出的3个三人组合都没有使消息走漏，那么可以判定未被选出的那个三人组合是泄密者，在这种情形下，步骤1所要考察的那个人（“9号”）不是泄密者.提供消息的次数最多为14+3=17（次），消息走漏的次数最多为2次（四人组必有一次，三人组至多一次）.

情形1-2　若8个人的这种14个四人组合皆未使消息走漏，则这8个人之外的那个人（“9号”）必为泄密者，这是因为上述的14个四人组合包含了8个人的所有三人组合，另外两个泄密者必在这8个人中，需要在步骤2中进一步讨论.

步骤2　在已经确定某人（“9号”）为泄密者的情况下，考察其余8人中任一被选定的人（例如“8号”）是否为泄密者？在得出否定结论时，通过本步骤可找到另外两个泄密者；在得出肯定结论时，为了找到第三个泄密者需要进入下一个步骤.

命题2　在7个人的三人组合中，存在7个三人组合，恰好包含这7个人的所有不同的二人组合（这样的7个三人组合并不唯一）.

证明　如果存在这样的三人组合，则其个数k2=7.事实上，如k2≠7，则因每一个三人组合包含3个二人组合，从而这k2个三人组合所包含的二人组合的个数为3k2≠21.但是，7个人的二人组合恰有21个，故k2=7.(www.xing528.com)

要完成命题2的证明，还要至少给出一种方法来寻找这7个三人组合.7个三人组合要包含21个二人组合，则任意两个三人组合所包含的二人组合各不相同，不妨以除“8号”之外的7个人为例，同样把这7个人两两分为四组（例如12，34，56，7），以下把含两个元素的组以双人组称呼，把含一个元素的组以单人组称呼.我们给出如下的方法：

（1）从双人组中任选一组和单人组组成一个三人组合，共有种选法.

（2）从双人组中每组各选一个元素.事实上，若选了两组中的两个元素，要使所选三人组合没有两个人相同，对另外一组的两个元素只能有一种选法.因此有种选法.

通过（1），（2）两步可找到7个三人组合来包含7个人的全部二人组合，并至少给出一种这样的7个三人组合为：

127，347，567，135，146，236，245.

操作2　对命题2证明中所给出的某一种7个三人组合，分别添加已在步骤1中确定的那个泄密者（“9号”），可构成7个四人组合，按任意顺序提供消息.

情形2-1　若某个四人组合使消息走漏，则要找的另外两个泄密者在该四人组除“9号”之外的三人中.由这三人可构成3个二人组合，任选其二，分别与“9号”构成两个三人组合，再提供消息（最多2次）.如果某个三人组合使消息走漏，则可找到另外两个泄密者；如果所选的三人组合皆未使消息走漏，则可断定没有被选的那个二人组合是泄密者，在这种情形下，步骤2所要考察的那个人（“8号”）不是泄密者.提供消息的次数最多为14+7+2=23次，消息走漏次数最多为2次（四人组必有一次，三人组至多一次）.

情形2-2　若上述的7个四人组合皆未使消息走漏，则第二个泄密者便是步骤2所要考察的那个人（“8号”），而第三个泄密者在已确定的两个泄密者之外的7个人中，需要在步骤3中进一步讨论.

步骤3　在已确定某二人（“9号”，“8号”）为泄密者的情况下，考察其余7个人中任一被选定的人（例如“7号”）是否为第三个泄密者？在得出否定结论时，通过本步骤可找到第三个泄密者；在得出肯定结论时，已找到了所有的泄密者.

命题3　在6个人的二人组合中，存在3个二人组合，恰好包含这6个人（这样的二人组合并不唯一）.

证明　命题显然成立.以1到6号为例，给出至少一种二人组合：

第一种：12，34，56；第二种：13，26，45；第三种：14，23，56.

操作3　对命题3证明中给出的某一种3个二人组合，分别添加已被确定的两个泄密者（“9号”，“8号”）可构成3个四人组合，按任意顺序发布消息.

情形3-1　若某个四人组合使消息走漏，则因为该组的四个人中已有两人确定为泄密者，故第三个泄密者在该组的另外两个人中，任选这两人中的一人与被确定的两个泄密者构成一个三人组合，再提供一次消息.如果消息走漏，则第三个泄密者便是被选入的那个人，如果消息没有走漏，则第三个泄密者是未被选入的那个人.在此情形下，步骤3中要考察的那个人（“7号”）不是泄密者.提供消息的次数最多为14+7+3+1=25（次），消息走漏的次数最多为两次（四人组必有一次，三人组最多一次）.

情形3-2　若上述3个四人组合皆未使消息走漏，则在步骤3中要考察的那个人（“7号”）就是第三个泄密者.在这种情形下，提供消息的次数最多14+7+3=24（次），消息走漏的次数为0次.

【模型评价】

本模型提出了直观的解决问题的方案，可操作性强，且环环紧扣，对问题的各项限制都恰好吻合，较为圆满地解决了问题.提供的方案具有一定的可选择性，不同的读者可根据各自实际情况及喜好选择不同的4人组合进行实际操作.不足之处为没有把模型推广为一般情形，如n个人中有m个泄密者的情况，上述方案可能不适用.

【模型优化】

若不限于只给4人组合发布消息，且取消走漏消息不超过两次的限制，则可能用更少的消息钓到泄密三人帮.一种可行的方案为：

在上述模型中，在考察某一个人（如“9号”）时，对其余8个人发布一次消息来看被考察的人是否为泄密者.若消息走漏，则被考察的人不是泄密者，在以后的讨论中不再考虑他；否则，被考察的人是泄密者，以后每次都给他发布消息.在未被考察过的人中任选一个进行下一步考察，以下同上，直到找出泄密者为止.一种可能的答案为：最多发布消息8次，最多走漏消息6次.但应注意，这种方法消息走漏次数太多，走漏率75%太大.

若取消最多提供消息25次的限制，则可先找出一种包含9人所有三人组合的四人组合，一种可行的包含9人所有三人组合的四人组合为：

提供消息至多23次，找到泄密的四人组合，再对其中的4个三人组至多发布消息3次，即可揪出泄密三人帮，消息至多走漏两次.