Olympiad Maths Prep

Track / Stage 6 / 316 of 400 #1316 of 2000

Problem 1316

National olympiad, first round
Combinatorics Difficulty 6.6 Find the answer

Two players AA and BB play a game with a ball and nn boxes placed onto the vertices of a regular nn-gon where nn is a positive integer. Initially, the ball is hidden in a box by player AA. At each step, BB chooses a box, then player AA says the distance of the ball to the selected box to player BB and moves the ball to an adjacent box. If BB finds the ball, then BB wins. Find the least number of steps for which BB can guarantee to win.

Official solution

1. Initial Setup: The ball is hidden in one of the nn boxes placed at the vertices of a regular nn-gon. Player AA hides the ball, and Player BB tries to find it. At each step, Player BB chooses a box, and Player AA reveals the distance of the ball to the chosen box and then moves the ball to an adjacent box.

2. Understanding the Distance: When Player BB chooses a box, Player AA reveals the distance of the ball to that box. This distance is the minimum number of steps along the edges of the nn-gon to reach the ball from the chosen box.

3. Movement of the Ball: After revealing the distance, Player AA moves the ball to an adjacent box. This means that the ball can only move to one of the two neighboring boxes.

4. **Strategy for Player BB**: To guarantee finding the ball, Player BB needs to systematically reduce the possible locations of the ball. The key is to use the information about the distance and the movement pattern of the ball.

5. Step-by-Step Strategy:
- Step 1: Player BB chooses any box, say box 11. Let the distance revealed be d1d_1.
- Step 2: Player AA moves the ball to an adjacent box. Now, the ball can be in one of the two boxes adjacent to the original box where it was.
- Step 3: Player BB chooses one of the two possible boxes where the ball could have moved. Let the new distance be d2d_2.
- Step 4: Player AA moves the ball again to an adjacent box. Now, Player BB has two possible locations for the ball again.
- Step 5: Player BB continues this process, each time narrowing down the possible locations of the ball based on the distances revealed and the movement pattern.

6. Guaranteed Win: To guarantee a win, Player BB needs to ensure that the ball is found within a finite number of steps. The strategy involves systematically checking each box and using the distance information to eliminate possibilities.

7. Least Number of Steps: The least number of steps required for Player BB to guarantee finding the ball can be determined by considering the worst-case scenario. In the worst case, Player BB needs to check each box at least once and use the distance information to track the ball's movement.

8. Conclusion: The least number of steps for which Player BB can guarantee to win is nn. This is because, in the worst case, Player BB needs to check each of the nn boxes once to ensure that the ball is found.

The final answer is n\boxed{n}.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.