Problem 567

Reciprocal games I

Tom has built a random generator that is connected to a row of n light bulbs. Whenever the random generator is activated each of the n lights is turned on with the probability of $\frac{1}{2}$ , independently of its former state or the state of the other light bulbs.

While discussing with his friend Jerry how to use his generator, they invent two different games, they call the reciprocal games:
Both games consist of n turns. Each turn is started by choosing a number k randomly between (and including) 1 and n, with equal probability of $\frac{1}{n}$ for each number, while the possible win for that turn is the reciprocal of k, that is $\frac{1}{k}$ .

In game A, Tom activates his random generator once in each turn. If the number of lights turned on is the same as the previously choosen number k, Jerry wins and gets $\frac{1}{k}$ , otherwise he will receive nothing for that turn. Jerry’s expected win after playing the total game A consisting of n turns is called $J_{A} (n)$ . For example $J_{A} (6) = 0.39505208$ , rounded to 8 decimal places.

For each turn in game B, after k has been randomly selected, Tom keeps reactivating his random generator until exactly k lights are turned on. After that Jerry takes over and reactivates the random generator until he, too, has generated a pattern with exactly k lights turned on. If this pattern is identical to Tom’s last pattern, Jerry wins and gets $\frac{1}{k}$ , otherwise he will receive nothing. Jerry’s expected win after the total game B consisting of n turns is called $J_{B} (n)$ . For example $J_{B} (6) = 0.43333333$ , rounded to 8 decimal places.

Let $S (m) = \sum_{n = 1}^{m} (J_{A} (n) + J_{B} (n))$ . For example S(6)=7.58932292, rounded to 8 decimal places.

Find S(123456789), rounded to 8 decimal places.

倒数游戏I

汤姆制作了一台连接着n个电灯泡的随机发电机。每次启动发电机，n个灯泡就会各自以 $\frac{1}{2}$ 的概率发光，每个灯泡是否发光与其之前的状态和其它灯泡是否发光均独立。

当他和朋友杰瑞讨论这台发电机时，他们发明了两个不同的游戏，都称为倒数游戏：这两个游戏都进行n轮，每一轮开始时先随机地在1到n（包括1和n）中等概率地选择一个整数k，这一轮的胜者收益将会是k的倒数，也就是 $\frac{1}{k}$ 。

在游戏A中，汤姆在每一轮中只启动随机发电机一次。如果发光的灯数和之前选择的数k一致，杰瑞获胜并获得收益 $\frac{1}{k}$ ，否则他这一轮没有收益。游戏A进行完整的n轮后，杰瑞的预期收益记为 $J_{A} (n)$ ，已知 $J_{A} (6) = 0.39505208$ ，保留8位小数。

在游戏B中，选定整数k后，汤姆不断地重启随机发电机，直至恰好有k个灯泡发光，然后由杰瑞接手发电机，不断重启直至再次出现有k个灯泡发光。如果杰瑞得到的k个发光灯泡恰好就是汤姆得到的k个发光灯泡，那么杰瑞获胜并获得收益 $\frac{1}{k}$ ，否则他这一轮没有收益。游戏B进行完整的n轮后，杰瑞的预期收益记为 $J_{B} (n)$ ，已知 $J_{B} (6) = 0.43333333$ ，保留8位小数。

记 $S (m) = \sum_{n = 1}^{m} (J_{A} (n) + J_{B} (n))$ 。已知S(6)=7.58932292，保留8位小数。

求S(123456789)并保留8位小数。