Maths Olympiad Prep

Library / /137 of 144

Combinatorics Difficulty 8.9 Shortlist Find the answer

Let nn be a positive integer. Two players AA and BB play a game in which they take turns choosing positive integers knk \le n. The rules of the game are:

(i) A player cannot choose a number that has been chosen by either player on any previous turn.
(ii) A player cannot choose a number consecutive to any of those the player has already chosen on any previous turn.
(iii) The game is a draw if all numbers have been chosen; otherwise the player who cannot choose a number anymore loses the game.

The player AA takes the first turn. Determine the outcome of the game, assuming that both players use optimal strategies.

*

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

In this game, both players A A and B B follow specific rules:
1. A player cannot choose a number that has already been chosen by either player.
2. A player cannot choose a number consecutive to any number the player has already chosen.
3. The game is a draw if all numbers have been chosen; otherwise, the player who cannot choose a number anymore loses.

Player A A makes the first move, always taking numbers such that they cannot take consecutive numbers in subsequent moves.

To find the outcome of this game for any n n , we need to analyze specific cases and determine the general pattern:

1. Base Cases:
- For n=1 n = 1 , Player A A chooses the only number available, and since no numbers are left for Player B B , the game ends with a draw.
- For n=2 n = 2 , Player A A can choose either number 1 1 or 2 2 . In either case, Player B B will have no available moves since the unchosen number is consecutive to A A's number, hence the game draws.
- For n=4 n = 4 , Player A A can choose one number, then B B chooses another such that it creates two separate ranges. Player A A cannot continue a sequence, and if both sets of choices for A A result in step-wise valid but non-winning positions for B B , resulting in a draw.
- For n=6 n = 6 , similar to the n=4 n = 4 , validating through moves results in non-winning sequences for both players if optimal play is performed, leading to a draw.

2. General Case Analysis:
- For n>6 n > 6 , Player A A 's strategy would lead to leaving isolated numbers for Player B B . Using optimal strategies, Player B B can always respond by either splitting A A 's group of non-consecutive numbers to maintain rounds until numbers are maximized or chosen, often resulting in Player B B winning.

3. Conclusion: By systematically analyzing numbers n6 n \leq 6 and making extrapolated strategic observations, we find:
For n{1,2,4,6}, the game ends in a draw. Otherwise, B wins. \text{For } n \in \{1, 2, 4, 6\} \text{, the game ends in a draw. Otherwise, } B \text{ wins.}

Hence, the outcome of the game can be represented as:
For n{1,2,4,6}, the game ends in a draw, else B wins. \boxed{\text{For } n \in \{1, 2, 4, 6\} \text{, the game ends in a draw, else } B \text{ wins}.}

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: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.