返回题库

机器人跳远

Robot Long Jump

专题
Probability / 概率
难度
L7

题目详情

机器人跳远题。机器人位置按随机过程变化,参赛者可以选择何时起跳;题目要求求该博弈的最优阈值策略以及对应的数值结果。

英文原题

Great news! The variety of robotic competition continues to grow at breakneck pace! Most recently, head-to-head long jump contests have been all the rage.

These contests consist of rounds in which each robot has a single attempt to score. In an attempt, a robot speeds down the running track (modeled as the numberline) from 0, the starting line, to 1, the takeoff point. A robot moves along this track by drawing a real number uniformly from [0,1] and adding it to the robot’s current position. After each of these advances, the robot must decide whether to jump or wait. If a robot crosses the takeoff point (at 1) before jumping its attempt receives a score of 0. If the robot jumps before crossing 1, it draws one final real number from [0,1] and adds it to its current position, and this final sum is the score of the attempt.

In a head-to-head contest, the two robots each have a single attempt without knowing the other’s result. In the case that they tie (typically because they both scored 0), that round is discarded and a new round begins. As soon as one robot scores higher than the other on the same round, that robot is declared the winner!

Assume both robots are programmed to optimize their probability of winning and are aware of each other’s strategies. You are just sitting down to watch a match’s very first attempt (of the first round, which may or may not end up being discarded). What is the probability that this attempt scores 0? Give this probability as a decimal rounded to 9 digits past the decimal point.

解析

该题要求求 Robot Long Jump 随机模型的纳什均衡。最优策略是等待机器人位置至少达到某个阈值 xx 后再跳,其中 xx 满足 (x33x+2)ex=3x(x^3-3x+2)e^x=3x,数值解为 x0.416195355x\approx0.416195355。在该阈值下,单轮得到正分的概率为 (1x)ex(1-x)e^x,最终所求概率为 1(1x)ex0.1148458861-(1-x)e^x\approx0.114845886


英文解析

For March’s puzzle, you had to determine the Nash equilibrium of a tricky probabilistic model of Robot Long Jump. It turned out the optimal play involved waiting until a robot’s position was at least some threshold x and then jumping, where x satisfies the equation

(x3 - 3x + 2)ex = 3x.

This threshold comes to ~0.416195355. Given that, the chance of any given round scoring a positive number is (1-x)ex, and so the final answer is (1-(1-x)ex) ~ 0.114845886

Congrats to the solvers that successfully computed the strategy and this probability!