Let the sequence on the paper be $X$.
First consider $n \neq 2k$. If the first digit of $X$ is 1, then on the blackboard there will be $C(n-1, k)$ sequences starting with 1, and $C(n-1, k-1)$ sequences starting with 0; note that $C(n-1, k) \neq C(n-1, k-1)$. From this we see that B only needs to count the number of sequences starting with 1 versus starting with 0 in order to determine what the first digit of $X$ is. Using the same method, B can determine every digit of $X$. Hence B can guess correctly on the very first try.

Now consider $n = 2k$. When $k = 1$, it is easy to see that two guesses are needed. When $k \ge 2$, note that if we flip every digit of $X$ on the paper (change 0 to 1 and 1 to 0), then the blackboard will still contain exactly the same set of sequences, so at least two guesses are required. Therefore, it suffices to show that two guesses are enough to guarantee the correct answer:

· If the first two digits of $X$ are the same, then on the blackboard, the sequences starting with 01 and those starting with 10 will each number $C(2k-2, k-1)$, while the sequences starting with 00 and those starting with 11 will each number $C(2k-2, k)$.

· Conversely, if the first two digits of $X$ are the same, then on the blackboard, the sequences starting with 01 and those starting with 10 will each number $C(2k-2, k)$, while the sequences starting with 00 and those starting with 11 will each number $C(2k-2, k-1)$.

· Since $C(2k-2, k-1) \neq C(2k-2, k)$, B only needs to count the corresponding numbers of sequences in order to determine whether the first two digits of $X$ are the same.

· By the same reasoning, B can determine whether any two digits of $X$ are the same.

· Therefore B only needs to guess what the first digit of $X$ is, and this requires at most two guesses. This completes the proof.