Mathematical and Physical Journal
for High Schools
Issued by the MATFUND Foundation
 Already signed up? New to KöMaL?

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