机器人射箭

Robot Archery

专题: Probability / 概率
难度: L7
来源: Jane Street

题目详情

经历了充满各种机器人体育赛事的令人疲惫的一年之后，我们迎来了本年度的最后一场赛事：机器人射箭。有四个机器人获得了今年决赛的资格，并按以下顺序被设为种子选手：

  机器人
  种子排位 

  Aaron
  1

  Barron  
  2

  Caren
  3

  Darrin 
  4

机器人将轮流向靶子^{1}射箭，从 Aaron 开始，并按种子顺序进行。轮到给定机器人时，他们射出一支箭。如果它比所有玩家的所有之前的箭更靠近靶心，该机器人将留在锦标赛中，走到队列的后面等待下一次轮到它。否则，该机器人将立即被淘汰。留在队列中的最后一名机器人是获胜者。

例如，以下是去年决赛的过程，其中 Caren 是获胜者。（奇怪的是，它涉及具有相同种子排位的相同机器人。）

  回合  
  机器人
  距离

  1
  Aaron
  10nm

  2
  Barron  
  8nm

  3
  Caren
  7nm

  4
  Darrin  
  1km

  5
  Aaron
  9nm

  6
  Barron
  2nm

  7
  Caren
  1nm

  8
  Barron
   $1Ym^{2}$

保留十位小数，Darrin 成为今年获胜者的概率是多少？（或者，如果你想发送精确答案，也可以！）

[1] 每个机器人的技能都是一样的。也就是说：对于靶子上任何具有非零面积的区域 R，在任何给定的射击中，所有机器人将箭射入 R 的正概率都是相同的。

[2] 这是一个大靶子。

After a grueling year filled with a wide variety of robot sporting events, we have arrived at the final event of the year: Robot Archery. Four robots have qualified for this year’s finals, and have been seeded in the following order:

Robot	Seed
Aaron	1
Barron	2
Caren	3
Darrin	4

The robots will take turns shooting arrows at a target¹, starting with Aaron and proceeding in order by seed. When it is a given robot’s turn, they shoot a single arrow. If it is closer to the center of the target than all previous arrows by all players, that robot remains in the tournament, going to the back of the queue to await their next turn. Otherwise that robot is eliminated immediately. The last robot remaining in the queue is the winner.

For example, here is how last year’s finals went, in which Caren was the winner. (Oddly enough it involved the same robots in the same seeding.)

Turn	Robot	Distance
1	Aaron	10nm
2	Barron	8nm
3	Caren	7nm
4	Darrin	1km
5	Aaron	9nm
6	Barron	2nm
7	Caren	1nm
8	Barron	1Ym²

To ten decimal places, what is the probability that Darrin will be this year’s winner? (Or, if you want to send in the exact answer, that’s fine too!)

[1] Each robot is equally skilled. Which is to say: for any region R on the target with nonzero area, the robots all have the same positive probability of landing an arrow within R on any given shot.

[2] It’s a large target.

解析

Original Explanation

[Above is a Mathematica-derived solution to the systems of equations described in the 4-player tournament described below]

Without loss of generality we can assume an arrow’s distance to the center of the target is U[0,1] distributed. Let P_j,k(x) denote the probability that Player j out of k in the current line will eventually win the game, given that the current best dart is at distance x.

In a 2-player archery tournament, we would have P_1,2(x) + P_2,2(x) = 1, P_1,2(0) = 0, and P_1,2(x) = ∫₀^x P_2,2(u) du. Taking derivatives of both sides in that last equation and substituing gives P‘_1,2(x) = −P_1,2(x). Solving gives P_1,2(x) = 1−e^−x.

In the 3-player version of the game, we get the following system of equations:

P_1,3(x) = ∫₀^x P_3,3(u) du

P_2,3(x) = (1 - x)P_1,2(x) + ∫₀^x P_1,3(u) du

P_1,3(x) + P_2,3(x) + P_3,3(x) = 1

P_1,3(0) = P_2,3(0) = 0.

And for the 4-player version we have the following:

P_1,4(x) = ∫₀^x P_4,4(u) du

P_2,4(x) = (1 - x)P_1,3(x) + ∫₀^x P_1,4(u) du

P_3,4(x) = (1 - x)P_2,3(x) + ∫₀^x P_2,4(u) du

P_1,4(x) + P_2,4(x) + P_3,4(x) + P_4,4(x) = 1

P_1,4(0) = P_2,4(0) = P_3,4(0) = 0.

In particular we have P_4,4(1) = (-5/4)*(cos(1) + sin(1)) + (1/2)*e^-1 + (e^-1/2)*(cos(sqrt(3)/2) + 5/sqrt(3)*sin(sqrt(3)/2)), or approximately 0.18343765086.

Congrats to this month’s solvers!