Problem A. 757. (September 2019)

A. 757. For every \(\displaystyle n\) non-negative integer let \(\displaystyle S(n)\) denote a subset of the positive integers, for which \(\displaystyle i\) is an element of \(\displaystyle S(n)\) if and only if the \(\displaystyle i\)-th digit (from the right) in the base two representation of \(\displaystyle n\) is a digit 1.

Two players, \(\displaystyle A\) and \(\displaystyle B\) play the following game: first, \(\displaystyle A\) chooses a positive integer \(\displaystyle k\), then \(\displaystyle B\) chooses a positive integer \(\displaystyle n\) for which \(\displaystyle 2^n\ge k\). Let \(\displaystyle X\) denote the set of integers \(\displaystyle \{0,1,\dots,2^n-1\}\), let \(\displaystyle Y\) denote the set of integers \(\displaystyle \{0,1,\dots,2^{n+1}-1\}\). The game consists of \(\displaystyle k\) rounds, and in each round player \(\displaystyle A\) chooses an element of set \(\displaystyle X\) or \(\displaystyle Y\), then player \(\displaystyle B\) chooses an element from the other set. For \(\displaystyle 1\le i\le k\) let \(\displaystyle x_i\) denote the element chosen from set \(\displaystyle X\), let \(\displaystyle y_i\) denote the element chosen from set \(\displaystyle Y\).

Player \(\displaystyle B\) wins the game, if for every \(\displaystyle 1\le i\le k\) and \(\displaystyle 1\le j\le k\) \(\displaystyle x_i<x_j\) if and only if \(\displaystyle y_i<y_j\) and \(\displaystyle S(x_i)\subset S(x_j)\) if and only if \(\displaystyle S(y_i)\subset S(y_j)\).

Which player has a winning strategy?

(Proposed by Levente Bodnár, Cambridge)

(7 pont)

Deadline expired on October 10, 2019.

Statistics:

1 student sent a solution.
0 point:	1 student.

Problems in Mathematics of KöMaL, September 2019