如何用数学方法来挑选满意的商品

你到商店去买东西，譬如说要买一个书包，商店售货员往往会拿出若干个书包供你挑选。你如何从这些书包中选出一个最满意的书包来呢？

当然，所谓满意与否要有一定的标准。一般顾客买东西大致有三个标准：一是商品质量要好；二是商品的式样要美观；三是价格要尽可能便宜。但是这三者往往不容易兼顾，而顾客的心理也各有差异，有人注意质量，有人注重款式，也有人看重价格。

这里，我们不去研究顾客的心理差异，而假定顾客心目中已经有一定的优劣标准，并且对商品甲和商品乙作比较时，顾客根据他的标准可以决定甲优于乙，还是乙优于甲。如果商品甲、乙难分高低，可在甲、乙中任取一个作为优胜者。

现在售货员已拿出n（n≥2）个书包a₁，…，a_n供你挑选，你如何从中选出一个最优的书包来呢？

根据心理学分析，人们对两个以上的对象同时进行比较是不容易进行的，因此一般总是采用两两比较的方法：先对其中两个对象进行比较，再换两个进行比较，如此进行多次，最后决定一个最优的对象。

而对n个书包a₁，作两两比较时，人们又总希望比较的次数愈少愈好。我们把能够保证选出的书包确是所有书包中的最佳者的最少比较次数记为f（n），要问：f（n）=？

如果n=2，即两个书包作比较选一个最优者，那么必须且只须比较一次，即可分出优劣，因此，f（2）=1。

如果n=3，即对三个书包a₁，a₂，a₃作两两比较。这时可先比较a₁，a₂，再将其中的优胜者（不妨设为a₂）与a₃比，挑选出来的优胜者（a₂或a₃）就是最优者。这样，经过两次比较就可选出最优者，而且比较次数不能少于2，否则是不可能决断出最优者来的。因此，f（3）=2。

对于一般情形的n个书包a₁，…，a_n，我们可以先对a₁与a₂进行一次比较，将优胜者与a₃比，再将优胜者与a₄比，如此继续，最后将a₁，…，a_n-1的优胜者与比，这样一共进行了n-1次比较，最后一次比较的优胜者就是最优书包。这一比较方案所用的比较次数一定不比f（n）小，因此，我们有f（n）＜n-1。

假设已经有一个方案经f（n）次比较选出其中的最优者，对于这一方案，第一次比较总是从n个书包中的某两个书包开始的。比了以后，其中的较差者已失去“冠军”资格，可以把它淘汰掉，于是就形成第一次比较的优胜者与其他n-2个书包（合起来为n-1个书包）来竞争“冠军”，其最少的比较次数是f（n-1）。而原方案去掉第一次比较剩留的比较方案恰好是n-1个书包选优的一种方案。因此，f（n）-1≥f（n-1）。

由于数字n的任意性，我们进一步可得

f（n）≥f（n-1）+1≥f（n-2）+1+1≥f（n-3）+3≥…≥f（n-（n-2））+（n-2）=f（2）+n-2

=1+（n-2）=n-1。

前面已经得到f（n）≤n-1，现在又证得f（n）≥n-1，于是，f（n）=n-1。

以上讨论说明，对于n个书包作两两比较选出最满意的书包，至少要作n-1次比较。前面我们已给出了一个作n-1次比较的方案，这当然是最佳方案。但是，最佳方案一般不是唯一的，读者不难自行给出其他的最佳方案来。

最后，我们提出一个较难的问题：要从n（n≥2）个书包中选出两个最优的书包来，如何进行两两比较呢？当然，我们希望得到最佳方案，并且要求比较的次数最少。需要说明的是，我们只要求能找出两个最满意的书包，而不必在这两个书包中再区分谁是冠军，谁是亚军。只要保证这两个书包确实比其余n-2个书包更优就行。

这个问题另一种提法是：设从n个书包中选出两个最佳者的最少比较次数记为g（n），问g（n）是多少？对于比较小的n值有下面的表（证明留给读者）：