0%

Problem 298


Problem 298


Selective Amnesia

Larry and Robin play a memory game involving of a sequence of random numbers between 1 and 10, inclusive, that are called out one at a time. Each player can remember up to 5 previous numbers. When the called number is in a player’s memory, that player is awarded a point. If it’s not, the player adds the called number to his memory, removing another number if his memory is full.

Both players start with empty memories. Both players always add new missed numbers to their memory but use a different strategy in deciding which number to remove:
Larry’s strategy is to remove the number that hasn’t been called in the longest time.
Robin’s strategy is to remove the number that’s been in the memory the longest time.

Example game:

Turn Called number Larry’s memory Larry’s score Robin’s memory Robin’s score
1 1 1 0 1 0
2 2 1,2 0 1,2 0
3 4 1,2,4 0 1,2,4 0
4 6 1,2,4,6 0 1,2,4,6 0
5 1 1,2,4,6 1 1,2,4,6 1
6 8 1,2,4,6,8 1 1,2,4,6,8 1
7 10 1,4,6,8,10 1 2,4,6,8,10 1
8 2 1,2,6,8,10 1 2,4,6,8,10 2
9 4 1,2,4,8,10 1 2,4,6,8,10 3
10 1 1,2,4,8,10 2 1,4,6,8,10 3

Denoting Larry’s score by L and Robin’s score by R, what is the expected value of |L-R| after 50 turns? Give your answer rounded to eight decimal places using the format x.xxxxxxxx.


选择性遗忘

拉里和罗宾正在玩一个记忆游戏,这个游戏需要一个在1到10之间的随机数组成的序列,每一轮按照序列叫一个数。每个玩家可以记住最多5个之前出现过的数。当叫到的数在玩家的记忆中时,该玩家得一分。如果不在,则玩家将这个被叫到的数加入他的记忆,如果记忆已经满了,需要先从中去掉另一个数。

两名玩家开始时记忆都是空的。在要去掉一个数的时候,两名玩家使用不同的策略:
拉里的策略是移除最久未被叫到的数。
罗宾的策略是移除在记忆中存在最久的数。

游戏样例:

轮数 被叫的数 拉里的记忆 拉里的得分 罗宾的记忆 罗宾的得分
1 1 1 0 1 0
2 2 1,2 0 1,2 0
3 4 1,2,4 0 1,2,4 0
4 6 1,2,4,6 0 1,2,4,6 0
5 1 1,2,4,6 1 1,2,4,6 1
6 8 1,2,4,6,8 1 1,2,4,6,8 1
7 10 1,4,6,8,10 1 2,4,6,8,10 1
8 2 1,2,6,8,10 1 2,4,6,8,10 2
9 4 1,2,4,8,10 1 2,4,6,8,10 3
10 1 1,2,4,8,10 2 1,4,6,8,10 3

记拉里的得分为L,罗宾的得分为R,在50轮后,|L-R|的期望值是多少?将你的答案四舍五入到八位小数,即格式为x.xxxxxxxx。