Problem 503
Compromise or persist
Alice is playing a game with n cards numbered 1 to n.
A game consists of iterations of the following steps.
(1) Alice picks one of the cards at random.
(2) Alice cannot see the number on it. Instead, Bob, one of her friends, sees the number and tells Alice how many previously-seen numbers are bigger than the number which he is seeing.
(3) Alice can end or continue the game. If she decides to end, the number becomes her score. If she decides to continue, the card is removed from the game and she returns to (1). If there is no card left, she is forced to end the game.
Let F(n) be the Alice’s expected score if she takes the optimized strategy to minimize her score.
For example, F(3) = 5/3. At the first iteration, she should continue the game. At the second iteration, she should end the game if Bob says that one previously-seen number is bigger than the number which he is seeing, otherwise she should continue the game.
We can also verify that F(4) = 15/8 and F(10) ≈ 2.5579365079.
Find F(106). Give your answer rounded to 10 decimal places behind the decimal point.
妥协还是坚持
爱丽丝在玩一个用标有1至n的n张卡片进行的游戏。
这个游戏不断重复进行以下步骤：
（1）爱丽丝随机地选择一张卡片。
（2）爱丽丝看不到这张卡片上的数，而她的一个朋友鲍勃可以看到，并告诉爱丽丝，在他之前看到过的数中，有多少个比这张卡片上的数要大。
（3）爱丽丝可以选择结束或继续游戏。如果她选择结束游戏，这个数将成为她的得分。如果她选择继续游戏，这张卡片从游戏中移除，并回到（1）。当游戏中没有卡片时，爱丽丝必须结束游戏。
记F(n)是爱丽丝采取最小化得分的最优策略时她的期望得分。
例如，F(3) = 5/3。在第一轮，她应当选择继续游戏，在第二轮，如果鲍勃告诉她前一个数比这一个数要大，她应选择结束游戏，否则她应选择继续游戏。
同样可以验证F(4) = 15/8以及F(10) ≈ 2.5579365079。
求F(106)，并将其四舍五入到小数点后10位小数作为你的答案。