MathDB
IMO Shortlist 2013, Combinatorics #8

Source: IMO Shortlist 2013, Combinatorics #8

July 9, 2014
combinatoricsgameinvariantIMO Shortlist

Problem Statement

Players AA and BB play a "paintful" game on the real line. Player AA has a pot of paint with four units of black ink. A quantity pp of this ink suffices to blacken a (closed) real interval of length pp. In every round, player AA picks some positive integer mm and provides 1/2m1/2^m units of ink from the pot. Player BB then picks an integer kk and blackens the interval from k/2mk/2^m to (k+1)/2m(k+1)/2^m (some parts of this interval may have been blackened before). The goal of player AA is to reach a situation where the pot is empty and the interval [0,1][0,1] is not completely blackened. Decide whether there exists a strategy for player AA to win in a finite number of moves.