MathDB

For every

n

non-negative integer let

S(n)

denote a subset of the positive integers, for which

i

is an element of

S(n)

if and only if the

i

-th digit (from the right) in the base two representation of

n

is a digit

1

.
Two players,

A

and

B

play the following game: first,

A

chooses a positive integer

k

, then

B

chooses a positive integer

n

for which

2^n\geqslant k

. Let

X

denote the set of integers

\{ 0,1,\dotsc ,2^n-1\}

, let

Y

denote the set of integers

\{ 0,1,\dotsc ,2^{n+1}-1\}

. The game consists of

k

rounds, and in each round player

A

chooses an element of set

X

Y

, then player

B

chooses an element from the other set. For

1\leqslant i\leqslant k

let

x_i

denote the element chosen from set

X

, let

y_i

denote the element chosen from set

Y

.
Player

B

wins the game, if for every

1\leqslant i\leqslant k

and

1\leqslant j\leqslant k

x_i<x_j

if and only if

y_i<y_j

and

S(x_i)\subset S(x_j)

if and only if

S(y_i)\subset S(y_j)

. Which player has a winning strategy?
Proposed by Levente Bodnár, Cambridge

Problem Statement