再出一個問題，與前一問題相關。也是找男女朋友的策略。
如果一個人一生只能遇到10個可能結婚的對象，他們當中是有合適不合適的差別，出現是隨機排列的，假設某人有能力記得所有過去出現在身邊的人選，並且能自由選擇，但是一旦結婚了，不能後悔。放棄不選的不能再回頭。請問他要使用什麼策略，才能在這十個對像中選到最適合的一個？這題是有答案的。
通常人的策略就是第一個就選了，還可能跳過一個，選後面出現比第一個更合適的。或跳過兩個。策略的意思就是說，要跳幾個，再拿後面的來比較，才可能有最大的機率選到最合適的？
本題沒有任何意味要人挑三揀四，純粹討論數學。
參考答案：
這題目是1979年一個數學雜誌刊出來的，真的較難。但是直覺來講一定是有答案。用電腦模擬就可以一個一個策略試出來，那一個最好。題目出處。
http://gurmeet.net/puzzles/horses-at-an-auction/
我嘗試把網上的講解用好懂的話語說出來。
首先考慮這個問題：如果有n個人選在列。挑選者跳過一個，再拿其餘的人選一個一個與第一個比較，選出最好的機率是多少？
假設這跳過的第一個是第 k好的人，換句話說有k-1個人比他好，會在後面出現。選中最好的機率就是（第k好的人出現在第一個的機率）x（k-1個比第一個更好人選裡面，最好的首先出現的機率）=（1/n） x （1/（k-1））。因為k-1個比第一個更好的，總有一個要最先出現被選到，誰最先？每一個的機率都是1/（k-1）。
我們現在把k從1到n全部加起來，就是最後選到第一的機率。就是：（1/n）(0+1+1/2+1/3+1/4+....+1/（n-1））
上式解釋如下: 第一個假如就是最好的，那後面再出現最好的機率就是0。第一個出現的假如是次好的。最好的在後面出現您的比例就是1。第一個是第三好，最好在後出現的機率就是1/2。同理類推。
整數數列相加，可以用積分來估計：
（1/n）(0+1+1/2+1/3+1/4+....+1/（n-1））> (1/n) integration_1^n-1 (1/n) (請看下面的積分式子) =(1/n)(log(n-1))。也就是把n個機率加起來，約等於對（1/n）的積分，從1積到n-1。結果就是 (1/n)*(log(n-1))。
請參照
https://en.wikipedia.org/wiki/Harmonic_series_(mathematics)
現在，把這個結果推到跳過h個可能最好人選。文中說：最好的人出現在後面的機率，出現在h=n/e的情形下，e=2.71828...。 （這部分還需要推導）。
結論是：10個人選，（h～=10/2.7）要選出最好的，先要跳過前三個看到的暫時最好者。找到最好的機率最高。
此題目不是要我們找對象時挑三揀四，因為我們的人選並沒有很多，而且情人眼裡出西施，一旦愛下去了之後，就完全失去判定好壞的能力了。建議，選前貨比三家不吃虧，選下去了，第一個就是最好的。別後悔了。
沒有留言:
張貼留言