Maths Olympiad Prep

Library / /1279 of 1394

Combinatorics Difficulty 6.0 AIME, harder Prove it United States

Problem:

Alice and Bob play a game on a circle with 88 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?

Solution

Solution:

Let the points be 0,,7(mod8)0, \ldots, 7 \pmod{8}, and view Alice's reveal as revealing the three possible locations of the apple. If Alice always picks 0,2,40,2,4 and puts the apple randomly at 00 or 44, by symmetry Bob cannot achieve more than 12\frac{1}{2}. Here's a proof that 12\frac{1}{2} is always possible.

Among the three revealed indices a,b,ca, b, c, positioned on a circle, two must (in the direction in which they're adjacent) have distance at least 33, so without loss of generality the three are 0,b,c0, b, c where 1b<c51 \leq b < c \leq 5. Modulo reflection and rotation, the cases are:

(0,1,2)(0,1,2): Bob places at 11 and wins.

(0,1,3)(0,1,3): Bob places at 11 half the time and 33 half the time, so wherever the apple is Bob wins with probability 12\frac{1}{2}.

(0,1,4)(0,1,4): Bob places at 11 or 44, same as above.

(0,2,4)(0,2,4): Bob places at 11 or 33, same as above.

(0,2,5)(0,2,5): Bob places at 11 or 55, same as above.

These cover all cases, so we're done.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.