机器人夺旗赛
Robot Capture-the-Flag
题目详情
中文译文待补充。
It’s been a while and change, but the Robot Games are back once again. This time it’s Capture the Flag!
Two robots, Aaron and Erin, have made it to this year’s final! Initially they are situated at the center of a unit circle. A flag is placed somewhere inside the circle, at a location chosen uniformly at random. Once the flag is placed, Aaron is able to deduce its distance to the flag, and Erin is only able to deduce its direction to the flag. (Equivalently: if (r, θ) are the polar coordinates of the flag’s location, Aaron is told r and Erin is told θ.)
Both robots are allowed to make a single move after the flag is placed, if they wish. Any move they make is without knowledge of what the other robot is doing. (And they may not move outside the circle.)
Whichever robot is closer to the flag after these moves captures the flag and is declared the winner!
During the preliminaries it was discovered that Erin is programmed to play a fixed distance along the detected angle θ. Assuming otherwise optimal play by both robots, can you determine the probability that Aaron will win? (Please express your answer to 10 decimal places.)
解析
中文解析待补充。
Original Explanation
Aaron has learned that Erin always plays a fixed distance — call it e — along the correct angle. Erin knows that Aaron knows this, and that Aaron will pick a distance a (and an angle at random, presumably) to maximize P(Aaron wins). So Erin should pick a value for e that minimizes this probability.
So we need to determine P(Aaron wins) for given values of e and r. If r is less than e/2, Aaron should choose to stay at the center, thus guaranteeing a win. Otherwise, Aaron should pick the distance a that maximizes the fraction of the circle of radius a located within a distance of |r−e| of the flag.
Maximizing the fraction of the circle of radius a inside the radius-|r−e| circle is equivalent to maximizing the subtended angle determined by the circles’ intersection points. This gives rise to the arcsin integral above. (The r multiplier inside both integrals and 2 multiplier generated by the bottom integral is to account for polar coordinates — e.g. if the flag has an ε probability of being placed in a tiny annulus of radius ≈δ, it has a 2ε probability of being placed in a tiny annulus of radius ≈2δ.)
Numerically solving for the e that minimizes the probability above gives e ≈ 0.501306994212753; plugging that into the integral above gives P(Aaron wins) ≈ 0.166186486474004.
Congrats to this month’s solvers!