MathDB
Game on [2^n-1] and [2^{n+1}-1]

Source: KöMaL A. 757

October 12, 2019
combinatorics

Problem Statement

For every nn non-negative integer let S(n)S(n) denote a subset of the positive integers, for which ii is an element of S(n)S(n) if and only if the ii-th digit (from the right) in the base two representation of nn is a digit 11.
Two players, AA and BB play the following game: first, AA chooses a positive integer kk, then BB chooses a positive integer nn for which 2n⩾k2^n\geqslant k. Let XX denote the set of integers {0,1,…,2n−1}\{ 0,1,\dotsc ,2^n-1\}, let YY denote the set of integers {0,1,…,2n+1−1}\{ 0,1,\dotsc ,2^{n+1}-1\}. The game consists of kk rounds, and in each round player AA chooses an element of set XX or YY, then player BB chooses an element from the other set. For 1⩽i⩽k1\leqslant i\leqslant k let xix_i denote the element chosen from set XX, let yiy_i denote the element chosen from set YY.
Player BB wins the game, if for every 1⩽i⩽k1\leqslant i\leqslant k and 1⩽j⩽k1\leqslant j\leqslant k, xi<xjx_i<x_j if and only if yi<yjy_i<y_j and S(xi)⊂S(xj)S(x_i)\subset S(x_j) if and only if S(yi)⊂S(yj)S(y_i)\subset S(y_j). Which player has a winning strategy?
Proposed by Levente Bodnár, Cambridge
Back to ProblemsView on AoPS