0%

Problem 444


Problem 444


The Roundtable Lottery

A group of p people decide to sit down at a round table and play a lottery-ticket trading game. Each person starts off with a randomly-assigned, unscratched lottery ticket. Each ticket, when scratched, reveals a whole-pound prize ranging anywhere from £1 to £p, with no two tickets alike. The goal of the game is for each person to maximize his ticket winnings upon leaving the game.

An arbitrary person is chosen to be the first player. Going around the table, each player has only one of two options:

  1. The player can scratch his ticket and reveal its worth to everyone at the table.
  2. The player can trade his unscratched ticket for a previous player’s scratched ticket, and then leave the game with that ticket. The previous player then scratches his newly-acquired ticket and reveals its worth to everyone at the table.

The game ends once all tickets have been scratched. All players still remaining at the table must leave with their currently-held tickets.

Assume that each player uses the optimal strategy for maximizing the expected value of his ticket winnings.

Let E(p) represent the expected number of players left at the table when the game ends in a game consisting of p players (e.g. E(111) = 5.2912 when rounded to 5 significant digits).

Let S1(N) = E(p)
Let Sk(N) = Sk-1(p) for k > 1

Find S20(1014) and write the answer in scientific notation rounded to 10 significant digits. Use a lowercase e to separate mantissa and exponent (e.g. S3(100) = 5.983679014e5).


圆桌彩票

一群共p个人决定围绕圆桌坐下玩一个彩票交易游戏。每个人在开始游戏时有一张随机分配的、未刮开的彩票,彩票刮开之后就会显示从£1至£p的一个随机整数数额,但没有两张彩票的数额相同。每个玩家进行游戏的目标是在离开游戏时最大化他的彩票收益。

随机选择一个人作为第一个玩家,然后游戏绕着圆桌一次进行,每个玩家有两个选项:

  1. 玩家可以刮开他的彩票,把彩票上的数额展示给所有人看。
  2. 玩家可以将自己未刮开的彩票和之前的玩家已经刮开的一张彩票进行交易,然后拿着已刮开的彩票离开游戏。拿到未刮开彩票的玩家将彩票刮开并展示给所有人看。

当所有彩票都已经刮开时,游戏结束。所有仍在场上的玩家必须拿着目前持有的彩票离开游戏。

假定所有玩家使用最优策略以最大化他的彩票收益。

对于由p个玩家进行的游戏,记E(p)是当游戏结束时还在圆桌上的人数期望值(例如E(111) = 5.2912,保留5位小数)。

记S1(N) = E(p)
记Sk(N) = Sk-1(p)对于k > 1

求S20(1014),并保留10位有效数字,用小写字母e分隔尾数和指数(例如,S3(100) = 5.983679014e5)。