OBM 2023 Problem 3

Seja $n$ um inteiro positivo. A humanidade vai começar a colonizar Marte. As agências SpaceY e SpaceZ serão as responsáveis por fazer as viagens entre os planetas. Para os foguetes não baterem, elas vão realizar viagens de forma alternada, sendo que a SpaceY fará a primeira viagem. Em cada viagem, a agência responsável realizará, conforme for possível, um entre dois tipos de missão:

(i) escolher um inteiro positivo $k$ e levar $k$ pessoas para Marte, criando uma nova colônia no planeta e estabelecendo-as nessa colônia;

(ii) escolher alguma colônia existente em Marte e um inteiro positivo $k$ estritamente menor que a população dessa colônia, e trazer $k$ pessoas dessa colônia de volta para a Terra.

Para manter a organização em Marte, uma missão não pode resultar em duas colônias com a mesma população e a quantidade de colônias deve ser no máximo $n$. A primeira agência que não puder realizar uma missão vai falir. Determine, em função de $n$, qual agência pode garantir que não falirá primeiro.