MathDB
Two-player game on [n]

Source: IMO 2015 Shortlist, C4

July 7, 2016
combinatoricsgameIMO Shortlist

Problem Statement

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.
Proposed by Finland