HMMT 二月 2016 · 冲刺赛 · 第 18 题

HMMT February 2016 — Guts Round — Problem 18

[ 11 ] Alice and Bob play a game on a circle with 8 marked points. Alice places an apple beneath one of the points, then picks five of the other seven points and reveals that none of them are hiding the apple. Bob then drops a bomb on any of the points, and destroys the apple if he drops the bomb either on the point containing the apple or on an adjacent point. Bob wins if he destroys the apple, and Alice wins if he fails. If both players play optimally, what is the probability that Bob destroys the apple?

解析

[ 11 ] Alice and Bob play a game on a circle with 8 marked points. Alice places an apple beneath one of the points, then picks five of the other seven points and reveals that none of them are hiding the apple. Bob then drops a bomb on any of the points, and destroys the apple if he drops the bomb either on the point containing the apple or on an adjacent point. Bob wins if he destroys the apple, and Alice wins if he fails. If both players play optimally, what is the probability that Bob destroys the apple? Proposed by: 1 Answer: 2 Let the points be 0 , . . . , 7 (mod 8), and view Alice’s reveal as revealing the three possible locations of the apple. If Alice always picks 0 , 2 , 4 and puts the apple randomly at 0 or 4, by symmetry Bob cannot 1 1 achieve more than . Here’s a proof that is always possible. 2 2 Among the three revealed indices a, b, c , positioned on a circle, two must (in the direction in which they’re adjacent) have distance at least 3, so without loss of generality the three are 0 , b, c where 1 ≤ b < c ≤ 5. Modulo reflection and rotation, the cases are: (0 , 1 , 2): Bob places at 1 and wins. (0 , 1 , 3): Bob places at 1 half the time and 3 half the time, so wherever the apple is Bob wins with 1 probability . (0 , 1 , 4): Bob places at 1 or 4, same as above. (0 , 2 , 4): Bob places at 1 or 3, same as 2 above. (0 , 2 , 5): Bob places at 1 or 5, same as above. These cover all cases, so we’re done.