最佳约会策略

作者:
系列:生活中的数学

查看该系列所有文章

这个问题有许多不同形式的阐述方式和变种,应用范围也很广。下面应该是比较吸引人和简单的那种,来自 姚期智 教授的理论计算机( I )的授课内容——我是其助教之一。


现假设你在 PIE 上征友,或者以其它方式,选定了某些约会对象,比如 \( n=20\) 个。约会当然得一个一个来,那么假设

  1. 可以将所有已约会的对象按优劣排序,但无法得知他们在所有的人里面的排名。在约会过程中,你知道某人是你目前已见到的最好的,但当时还不能确定是不是所有人里面最好的。
  2. 如果你在约会当时决定放弃某人,后面再没有机会和此人和好——好马不吃回头草。
  3. 选定意中人后,约会结束——骑驴找马是不道德的。

OK ,现在目标当然是找到你心目中最喜欢的人。关系定得太早,会因为第 2 条假设——精彩的还在后头,定得太晚,会因为第 3 条——而后悔莫及。所以,什么策略才能让你以最大概率找到你最满意的那个人呢?

一个简单而且自然的方法是,待定 \( k\) ,与前 \( k\) 个人约会,不做任何选择。继续约会直到遇到比这前 \(k\) 个人还好的那个人为止。

对给定的 \(k\) ,我们可以计算选中最好的人的概率。假设最好的人出现在第 \(i\) 位( \(i>k\) ),我们选中它的概率为 \(\frac{k}{i-1}\) 。这是因为这等价于前 \(i-1\) 个人的最高分出现在前 \(k\) 个人。

这样,选中最好的人的概率为:

$$ \begin{eqnarray} P &=& \sum_{i=k+1}^n \frac{1}{n} \frac{k}{i-1} \\ &=& \frac{k}{n}\sum_{i=k+1}^n \frac{1}{i-1} \\ &\approx & \frac{k}{n} \ln \frac{n}{k} \end{eqnarray} $$

接下来就是一个简单求 \(\frac{x}{\ln x}\) 的问题,其中 \(x=\frac{n}{k}\) 。对该表达式求导可知在 \(x=e\) ,亦即 \(k=\frac{n}{e} \approx 0.37n\) 时取到最大值。对于 \(n=20\) ,大约先过滤前 \(0.37n\approx 7\) 个人时,有最大 40%的概率选中最好的那个人,有接近 70%的概率选中最好或者此好的那个人。

我们还可以证明,在所有可能的策略之中,上面的策略都是最优的。(证明在此: 37 rule is optimal )。

这个问题在日常生活中有更多应用。比如你打算在 30 岁前结婚,现在 20 岁。那么在 24 岁前先别确定目标, 24 岁以后遇到比之前都好的就可以定下来。这几乎就是你能达到最好的结果了——假设你的候选人在这十年是均匀或者随机出现的。

这种策略也许能说明为何初恋成功率低?

以上所用都是爱情和婚姻的简化模型,没有考虑爱情中的主观因素。所以,请只把它当作一个脑力游戏。

Q. E. D.

系列: 生活中的数学 »
在大家玩牌的时候,每一局之前都需要重新洗牌——一次洗牌指将牌分为左右两垛然后穿插放牌,但多少次洗牌才是正当的呢?就我多次打牌的观察,多数人都不超过 4 次。
后一篇:
注:来凑凑热闹,最先在 槽边往事 看到的,不过网上已经有相当多的 讨论
在大家玩牌的时候,每一局之前都需要重新洗牌——一次洗牌指将牌分为左右两垛然后穿插放牌,但多少次洗牌才是正当的呢?就我多次打牌的观察,多数人都不超过 4 次。
数学 » 搞笑, 数学之美
来自 University of WarwickMike Paterson 星期二在 Yao 的理论计算机课堂上给了一个非常有趣的小讲座。