International Mathematical Olympiad

The game can be reformulated in an equivalent one: The player $A$ chooses an element $x$ from the set $S$ (with $|S| = N$) and the player $B$ asks the sequence of questions. The $j$-th question consists of $B$ choosing a set $D_j \subseteq S$ and player $A$ selecting a set $P_j \in \{Q_j, Q_j^C\}$. The player $A$ has to make sure that for every $j \ge 1$ the following relation holds:
$$x \in P_j \cup P_{j+1} \cup \dots \cup P_{j+k}.$$
The player $B$ wins if after a finite number of steps he can choose a set $X$ with $|X| \le n$ such that $x \in X$.

a.
It suffices to prove that if $N \ge 2^k + 1$ then the player $B$ can determine a set $S' \subseteq S$ with $|S'| \le N - 1$ such that $x \in S'$.

Assume that $N \ge 2^k + 1$. In the first move $B$ selects any set $D_1 \subseteq S$ such that $|D_1| \ge 2^{k-1}$ and $|D_1^C| \ge 2^{k-1}$. After receiving the set $P_1$ from $A$, $B$ makes the second move. The player $B$ selects a set $D_2 \subseteq S$ such that $|D_2 \cap P_1^C| \ge 2^{k-2}$ and $|D_2^C \cap P_1^C| \ge 2^{k-2}$. The player $B$ continues this way: in the move $j$ he/she chooses a set $D_j$ such that $|D_j \cap P_j^C| \ge 2^{k-j}$ and $|D_j^C \cap P_j^C| \ge 2^{k-j}$.

In this way the player $B$ has obtained the sets $P_1, P_2, \dots, P_k$ such that $(P_1 \cup \dots \cup P_k)^C \ge 1$. Then $B$ chooses the set $D_{k+1}$ to be a singleton containing any element outside of $P_1 \cup \dots \cup P_k$. There are two cases now:

Case 1. The player $A$ selects $P_{k+1} = D_{k+1}^C$. Then $B$ can take $S' = S \setminus D_{k+1}$ and the statement is proved.

Case 2. The player $A$ selects $P_{k+1} = D_{k+1}$. Now the player $B$ repeats the previous procedure on the set $S_1 = S \setminus D_{k+1}$ to obtain the sequence of sets $P_{k+2}, P_{k+3}, \dots, P_{2k+1}$. The following inequality holds:
$$|S_1 \setminus (P_{k+2} \cdots P_{2k+1})| \ge 1,$$
since $|S_1| \ge 2^k$. However, now we have
$$|(P_{k+1} \cup P_{k+2} \cup \dots \cup P_{2k+1})^C| \ge 1,$$
and we may take $S' = P_{k+1} \cup \dots \cup P_{2k+1}$.

b.
Let $p$ and $q$ be two real numbers such that $1.99 < p < q < 2$. Let us choose $k_0$ such that
$$\left(\frac{p}{q}\right)^{k_0} \le 2 \cdot \left(1 - \frac{q}{2}\right) \quad \text{and} \quad p^k - 1.99^k > 1.$$
We will prove that for every $k \ge k_0$ if $|S| \in (1.99^k, p^k)$ then there is a strategy for the player $A$ to select sets $P_1, P_2, \dots$ (based on sets $D_1, D_2, \dots$ provided by $B$) such that for each $j$ the following relation holds:
$$P_j \cup P_{j+1} \cup \dots \cup P_{j+k} = S.$$
Assuming that $S = \{1, 2, \dots, N\}$, the player $A$ will maintain the following sequence of $N$-tuples: $(\mathbf{x})_{j=0}^{\infty} = (x_1^0, x_2^0, \dots, x_N^0)$. Initially we set $x_1^0 = x_2^0 = \dots = x_N^0 = 1$. After the set $P_j$ is selected then we define $\mathbf{x}^{j+1}$ based on $\mathbf{x}^j$ as follows:
$$x_i^{j+1} = \begin{cases} 1, & \text{if } i \in P_j \\ q \cdot x_i^j, & \text{if } i \notin P_j. \end{cases}$$
The player $A$ can keep $B$ from winning if $x_i^j \le q^k$ for each pair $(i, j)$. For a sequence $\mathbf{x}$, let us define $T(\mathbf{x}) = \sum_{i=1}^N x_i$. It suffices for player $A$ to make sure that $T(\mathbf{x}^j) \le q^k$ for each $j$.

Notice that $T(\mathbf{x}^0) = N \le p^k < q^k$.

We will now prove that given $\mathbf{x}^j$ such that $T(\mathbf{x}^j) \le q^k$, and a set $D_{j+1}$ the player $A$ can choose $P_{j+1} \in \{D_{j+1}, D_{j+1}^C\}$ such that $T(\mathbf{x}^{j+1}) \le q^k$. Let $\mathbf{y}$ be the sequence that would be obtained if $P_{j+1} = D_{j+1}$, and let $\mathbf{z}$ be the sequence that would be obtained if $P_{j+1} = D_{j+1}^C$. Then we have
$$T(\mathbf{y}) = \sum_{i \in D_{j+1}^C} q x_i^j + |D_{j+1}|$$
$$T(\mathbf{z}) = \sum_{i \in D_{j+1}} q x_i^j + |D_{j+1}^C|.$$
Summing up the previous two equalities gives:
$$T(\mathbf{y}) + T(\mathbf{z}) = q \cdot T(\mathbf{x}^j) + N \le q^{k+1} + p^k, \text{ hence}$$
$$\min \{T(\mathbf{y}), T(\mathbf{z})\} \le \frac{q}{2} \cdot q^k + \frac{p^k}{2} \le q^k,$$
because of our choice of $k_0$.