Let $k$ and $n$ be two non-zero natural numbers, such that $k \leqslant 2^{n}$. Morgane has written, in her notebook, the set of $n$-tuples formed of 0 and 1: there are $2^{n}$ of them. We say that two $n$-tuples $\left(x_{1}, \ldots, x_{n}\right)$ and $\left(y_{1}, \ldots, y_{n}\right)$ are neighbors if they have $n-1$ terms in common, that is, if there is only one integer $i$ such that $x_{i} \neq y_{i}$. Then Morgane chooses $k$ of these $n$-tuples and underlines them. She then performs the following operations: in each operation, she chooses an $n$-tuple whose two neighbors are underlined, and she also underlines this $n$-tuple.
For which values of $k$ can Morgane manage to underline all the $n$-tuples?
Throughout the following, we will identify our $n$-tuples with vectors in $(\mathbb{Z} / 2 \mathbb{Z})^{n}$, that is, vectors whose $n$ coordinates are elements of $\mathbb{Z} / 2 \mathbb{Z}$. Thus, we denote:
$\triangleright 0$ the vector whose all coordinates are zero,
$\triangleright \mathbf{a}_{i}$ the vector whose $i^{\text{th}}$ coordinate is 1 and the others are 0,
$\triangleright \mathbf{b}_{i, j}$ the vector whose $i$-th and $j^{\text{th}}$ coordinates are 1 and the others are 0;
First, we will show that the integer $k=1+\lceil n / 2\rceil$ works, where $\lceil x\rceil$ denotes the ceiling of the real number $x$, that is, the smallest integer greater than or equal to $x$. To do this, we can assume that Morgane first underlined the vectors $\mathbf{0}, \mathbf{b}_{1,2}, \mathbf{b}_{3,4}, \ldots, \mathbf{b}_{2 k-3,2 k-2}$; if $n$ is even, the last vector is $\mathbf{b}_{n-1, n}$ and, if $n$ is odd, by abuse of notation, we identify the vector $\mathbf{b}_{n, n+1}$ with the vector $\mathbf{a}_{n}$. Under these conditions:
$\triangleright$ if $i$ is even, then $\mathbf{a}_{i}$ is a neighbor of the two vectors $\mathbf{0}$ and $\mathbf{b}_{i-1, i}$;
$\triangleright$ if $i$ is odd, with $i \leqslant n-1$, then $\mathbf{a}_{i}$ is a neighbor of the two vectors $\mathbf{0}$ and $\mathbf{b}_{i, i+1}$;
$\triangleright$ if $i=n$ is odd, then $\mathbf{a}_{i}=\mathbf{a}_{n}=\mathbf{b}_{2 k-3,2 k-2}$ is already underlined.
Thus, Morgane can underline each of the vectors $\mathbf{a}_{i}$.
An immediate induction on $\ell$ then shows that Morgane can underline any vector with $\ell$ coordinates equal to 1, and the $n-\ell$ others equal to 0. We conclude that any integer $k$ between $1+\lceil n / 2\rceil$ and $2^{n}$ works.
Conversely, let $k$ be one of the integers sought: let us show that $k \geqslant 1+\lceil n / 2\rceil$. To do this, we first construct the directed graph whose vertices are the vectors in $(\mathbb{Z} / 2 \mathbb{Z})^{n}$ and whose edges are constructed as follows:
$\triangleright$ if a vector $\mathbf{t}$ was one of the $k$ vectors that Morgane had initially underlined, then no edge arrives at $\mathbf{t}$;
$\triangleright$ otherwise, let $\mathbf{u}$ and $\mathbf{v}$ be two neighbors of $\mathbf{t}$ that Morgane had underlined before underlining $\mathbf{t}$: the graph contains an edge from $\mathbf{u}$ to $\mathbf{t}$, and another edge from $\mathbf{v}$ to $\mathbf{t}$.
Now introduce some notions and concepts. We say that a set $S$ of vectors is an initial set if every edge entering a vertex of $S$ comes from another vertex of $S$. We also say that $S$ is connected if, by taking the edges in the wrong direction, we can connect any vector in $S$ to any other without leaving $S$. Furthermore, we say that the sources of $S$ are the vectors in $S$ that Morgane had initially underlined, that is, those in which no edge enters. Finally, we say that a coordinate $i$ is a variable of $S$ if there exist two vectors $\mathbf{t}$ and $\mathbf{t}^{\prime}$ in $S$ such that $\mathbf{t}_{i} \neq \mathbf{t}_{i}^{\prime}$.
We will now prove the property $\mathcal{P}_{\ell}$ by strong induction on $\ell$:
Let $S$ be an initial connected set containing $\ell$ vectors and $m$ sources. Then $S$ has at most $2(m-1)$ variable coordinates.
First, the property $\mathcal{P}_{1}$ is obvious, since $S$ is then reduced to a single vector, which is itself a source, and therefore has no variable coordinate. Now let $\ell \geqslant 2$ be an integer such that the properties $\mathcal{P}_{1}, \ldots, \mathcal{P}_{\ell-1}$ are all true, and let $S$ be an initial connected set containing $\ell$ vectors, $m$ sources, and $c$ variable coordinates.
Let $\mathbf{t}$ be the last vector, among those belonging to $S$, that Morgane underlined. If $\mathbf{t}$ is a source, then $S$ is formed only of sources, which contains no edge, in contradiction with the fact that $S$ is connected and that $\ell \geqslant 2$. Thus, there exist two edges $\mathbf{u} \rightarrow \mathbf{t}$ and $\mathbf{v} \rightarrow \mathbf{t}$, coming from two other vectors $\mathbf{u}$ and $\mathbf{v}$ in $S$. Let $i$ and $j$ be the two coordinates such that $\mathbf{t}_{i} \neq \mathbf{u}_{i}$ and $\mathbf{t}_{j} \neq \mathbf{v}_{j}$, and let $S^{\prime}$ be the set $\backslash \backslash\{\mathbf{t}\}$.
$\triangleright$ If $S^{\prime}$ is connected, we easily observe that the variable coordinates of $S$ are those of $S^{\prime}$. Since $S^{\prime}$ contains $\ell-1$ vertices and $m$ sources, the sets $S$ and $S^{\prime}$ therefore have at most $2(m-1)$ variable coordinates.
$\triangleright$ If $S^{\prime}$ is not connected, then we can split it into two initial connected sets, $U$ and $V$, which contain the vectors $\mathbf{u}$ and $\mathbf{v}$, respectively. One contains $\ell_{u}$ vectors, $m_{u}$ sources, and $c_{u}$ variable coordinates, while the other contains $\ell_{v}$ vectors, $m_{v}$ sources, and $c_{v}$ variable coordinates. Since $\ell_{u} \leqslant \ell-1$ and $\ell_{v} \leqslant \ell-1$, we know that $c_{u} \leqslant 2\left(m_{u}-1\right)$ and that $c_{v} \leqslant 2\left(m_{v}-1\right)$.
Moreover, the sources of $S$ are those of $U$ and $V$, and no source can belong to both $U$ and $V$, so $m=m_{u}+m_{v}$. On the other hand, we easily observe that the variable coordinates of $S$ are either those of $U$, those of $V$, or $i$ and $j$. Thus, the set $S$ has at most $c_{u}+c_{v}+2 \leqslant 2\left(m_{u}+m_{v}-1\right)=2(m-1)$ variable coordinates, which proves $\mathcal{P}_{\ell}$.
Finally, note that the set $(\mathbb{Z} / 2 \mathbb{Z})^{n}$ itself is an initial connected set, and it contains $n$ variables and $k$ sources. The property $\mathcal{P}_{2^{n}}$ therefore shows that $n \leqslant 2(k-1)$, that is, $k \geqslant 1+\lceil n / 2\rceil$. The integers sought are therefore the integers between $1+\lceil n / 2\rceil$ and $2^{n}$.