The answer is $n$ (except in the degenerate case $n = 1$, when it is 2). We examine the case $n \ge 2$ only. A valid construction is to color all strings with a single 1. Now we show $n-1$ initially colored strings does not suffice. Let a subset $S \subseteq \mathbb{F}_2^n$ be round if any string adjacent to two elements of $S$ is itself in $S$. Considering initially colored strings $s_1, \dots, s_{n-1}$, their span is a hypercube $K$ of dimension at most $n-1$ and is round, so no non-$K$ string will ever be colored.

Any more elementary solutions?

Rickyminer wrote: Any more elementary solutions? Isn't hyper-cube elementary?

@CantonMathGuy Wrong solution. Actually, this part is not True: CantonMathGuy wrote: Considering initially colored strings $s_1, \dots, s_{n-1}$, their span is a hypercube $K$ of dimension at most $n-1$ and is round. As for n=4 the answer is 3. Three strings 0000,1100, and 0011 suffice. The original statement of the problem: Initially, k vertices of a n-dimensional hypercube are black. In each step, a vertex with at least two black neighbours gets black. Find the least possible k, such that the whole hypercube will be black eventually.

Etemadi wrote: @CantonMathGuy Wrong solution. Actually, this part is not True: CantonMathGuy wrote: Considering initially colored strings $s_1, \dots, s_{n-1}$, their span is a hypercube $K$ of dimension at most $n-1$ and is round. As for n=4 the answer is 3. Three strings 0000,1100, and 0011 suffice. The original statement of the problem: Initially, k vertices of a n-dimensional hypercube are black. In each step, a vertex with at least two black neighbours gets black. Find the least possible k, such that the whole hypercube will be black eventually. Do you know what is the answer?If so can you post that?Thanks in advance.

Bump this

Here are the steps written in the grading schem.I don't know how to prove the third part but the first two parts are really trivial if you know what you are going to prove. Let $T(n)$ be the answer of problem: 1.$T(n) \le \lfloor \frac{n+2}{2} \rfloor$($5$ marks) 2.$T(n) \ge T(n-1)$($2$ marks) 3.$T(n+2) \ge T(n)+1$($3$ marks)

Construction: For even $n$, these $\lceil \frac {n}{2} \rceil +1$ strings work: (Odd's are similar) $110\dots 0$ , $00110\dots 0$ , $0000110\dots0 $, $\cdots $ , $0\dots011$ and $00\dots 0$. Use induction to prove this. Proof: By losing dimension $n$, I mean forming a new hypercube such that string $a_{1},a_{2},\dots ,a_{n-1}$ is colored, if $a_{1},a_{2},\dots ,a_{n-1},0$ or $a_{1},a_{2},\dots ,a_{n-1},1$ is colored. (Project two (n-1)-dimensional hypercubes onto each other) First prove that $T(n)\ge T(n-1)$, which is kinda obvious. Just lose one arbitrary dimension. If the previous  $T(n)$ points could color the n-dimensional hypercube, then these new ones can color the remaining (n-1)-dimension hypercube. Next, $T(n+2)\ge T(n)+1$. This is similar. Consider one correct coloring of (n+2)-dimensional hypercube. Let A be the first point which gets colored. So there are two points B,C differing in only one dimesion with A. Let these dimensions be $i,j$ respectively. Now lose dimensions $i,j$. At least one colored point is reduced. So there is a coloring of n-dimensional hypercube using at most $T(n+2)-1$ initial colored points. Now use induction to reach the initial claimed bound. P.S: I'll post another beautiful solution later.

Quote: P.S: I'll post another beautiful solution later. Waiting for this!

I'm back to finish Etemadi's beautiful solution. It was from the official solution, a marvelous and short proof. And I can't help sharing it. Let the n-dimension hypercube be $Q_n$. The main claim is that Claim. At any time, a connected component in $Q_n$ with $x$ initial black vertices has diameter at most $2x-2$. Proof. Initially, a connected component with $x$ black vertices has diameter at most $x-1$, since each of them are initially black. When two connected components with $x,y$ initial black vertices, respectively, merged, the new connected components has diameter at most $$(2x-2)+2+(2y-2)=2(x+y)-2$$since newly-colored black vertices are adjacent to both components, at most $2$ is added. $\blacksquare$ By the above claim, we must have $2k-2 \ge n$, i.e. $k \ge \lceil \tfrac{n}{2} \rceil +1$.