Question 75
Let $k$ and $n$ be positive integers with $k \leqslant 2^{n}$. Morgane writes down all $n$-tuples of zeros and ones, of which there are $2^{n}$. Two $n$-tuples $\left(x_{1}, \ldots, x_{n}\right)$ and $\left(y_{1}, \ldots, y_{n}\right)$ are neighbors if they agree in $n-1$ coordinates, meaning exactly one integer $i$ satisfies $x_{i} \neq y_{i}$. She chooses $k$ of these $n$-tuples and underlines them. At each subsequent step she may underline an $n$-tuple with two already underlined neighbors, thereby underlining this $n$-tuple.
For which values of $k$ can she underline every $n$-tuple?
For which values of $k$ can she underline every $n$-tuple?