Let $n$ be a positive integer. Alice and Bob play the following game. First, Alice picks $n + 1$ subsets $A_1,...,A_{n+1}$ of $\{1,... ,2^n\}$ each of size $2^{n-1}$. Second, Bob picks $n + 1$ arbitrary integers $a_1,...,a_{n+1}$. Finally, Alice picks an integer $t$. Bob wins if there exists an integer $1 \le i \le n + 1$ and $s \in A_i$ such that $s + a_i \equiv t$ (mod $2^n$). Otherwise, Alice wins. Find all values of $n$ where Alice has a winning strategy.
Problem
Source: 2021 Nordic MC p3
Tags: combinatorics, number theory
16.05.2021 16:50
We will show Bob always wins, that is, there is no value of $n$ for which Alice has a winning strategy. First, let's translate the problem into more comprehensive form. So, Alice picks $n+1$ subsets $A_1,A_2,\dots,A_{n+1}$ of residues modulo $2^n.$ Then Bob chooses $n+1$ offsets (integers) $a_1,\dots,a_{n+1}.$ He wins if the subsets $A_i+a_i,i=1,2,\dots,n+1$ cover the base set of all residues modulo $2^n.$ Here, by $A+b$ we denote the set $\{a+b : a\in A\}$ and hereafter all subsets are taken modulo $2^n.$ The strategy of Bob is a greedy one in some sense. He picks $a_1=0$ and at every step he tries to cover as many residues as possible from the still uncovered ones. The main observation is that he can cover at least half of them. Lemma. Let $A, X$ are subsets of residues modulo $2^n$ and $|A|=2^{n-1}.$ Then there exists an integer $a$ such that $A+a$ covers at least half of the elements of $X.$ Proof. Fix some $x\in X.$ Pick randomly a residue $a$ modulo $2^n.$ Let $\xi_x$ be the random variable that is $1$ if $x\in A+a$ and $0$ otherwise. Obviously, there is exactly $1/2$ chance that $\xi_x$ takes value $1,$ because for exactly half of all residues $a$ we have $x\in A+a,$ due to $|A|=2^{n-1}.$ Consider the random variable $\xi:=\sum_{x\in X}\xi_x.$ The value of $\xi$ just shows how many elements of $X$ are covered by $A+a.$ By the linearity of expectation $$\mathbb{E}[\xi]=\sum_{x\in X}\mathbb{E}[\xi_x]=\sum_{x\in X}\frac{1}{2}=\frac{|X|}{2}.$$It means that for some offset $a$ the random variable $\xi$ takes value at least $|X|/2$ and the result follows. $\blacksquare$ Thus, Bob chooses $a_1=0$ and let the set of uncovered residues be $X_2, |X_2|=2^{n-1}.$ At each consecutive step $i=2,3,\dots,n+1$, he chooses $a_i$ such that $A_i+a_i$ covers at lest half of the elements of $X_i$ and let $X_{i+1}$ be the set of still uncovered ones. Clearly, after $n+1$ steps he will manage to cover all the residues.