(redacted)

Let $A$ be the number that the team leader choose , and let $S(A)$ be the set of the numbers writen by the deputy leader For each number $T$ in $S$ , there is a set of $\binom{n}{k}$ elements that contains the numbers that have exacly $k$ digits different from $T$. Let this set be $F(T)$ And , because $A \in F(T)$ $\forall T \in $ $S$ so the intersection of these set is at least 1 . Now we consider 2 cases Case 1 : $n = 2k$ . Then , let $A'$ be the number that has every digits different from $A$ Let $A = \overline{a_1a_2..a_n}_{(2)}$ and $A' = \overline{b_1b_2...b_n}_{(2)}$ Now for an abitrary numbers $R$ on the paper of the deputy leader , if the digits $a_{i_1} , a_{i_2},..,a_{i_k}$ of $A$ are changed , we change the $k$ digits $b_j (j \neq i_t , t = \overline{1,k})$ of $A'$ then receive the number $T$, which is equal to $R$ Then we have $S(A) = S(A')$ , which implies that the intersection of every $F(T)$ is bigger than $2$, which implies that the contestant must guess at least 2 times Case 2 : $n \neq 2k$ . Suppose that the contestant must guess more than one time, that means , the intersection of every $F(T)$ is bigger than $1$ This is equivalent to exist a number $B = \overline{b_1b_2..b_n}_{(2)}$ such that for every way to change $k$ digits in $B$ , we can find a way to change $k$ digits in $A$ to receive the same number If $A,B$ has very digits different. So , we change the $k$ first digits of $B$ and receive number $R$ has $k$ first digits equal to $A$'s, and the last $n-k$ digits are different. Then We must change the last $n-k$ last digits of $A$ to receive the number equal to $R$. Then $k = n-k$ which is a contradiction If $A,B$ have $t$ equal numbers. For convinient, we move these $t$ digits to the beginning of $A,B$ $A = \overline{a_1a_2...a_tc_1c_2...c_{n-t}}_{(2)}$ and $B = \overline{a_1a_2...a_t(1-c_1)(1-c_2)...(1-c_{n-t})}_{(2)}$ It's clear that $ t \leq k$ , because , if $t > k$ , we change $a_1,...,a_k$ in $B$ so we must also change $a_1,..,a_k$ in $A$ Now , we change $q$ digits $a_1...a_q$ in $A$ for some $q \leq t$, will choose later , and change $k-q$ digits $c_1,...,c_{k-q}$ So $B$ must be changed exacly the digits $a_1,..,a_q$ and $(1-c_{k-q+1}) ,...,(1-c_{n-t})$, which is $n-t-k+2q$. Then $n-t-k+2q = k \implies 2q = 2k+t-n$ So , if $t \leq 1$, we choose $q = 0,1$ then $0 = 2 = 2k+t -n$ which is a contradiction Then , for $n = 2k$, the contestant need to guess $2$ times ; and for $n \neq 2k$, the contestant only need to guess $1$ time

Note that you can find the first number of the binary sequence unless $n=2k$. Now we purceed by recursion, if $n=2k$ we will have 2 cases but each of one of this case will reduce to an trivial one because we wont have $n=2k$ anymore. If $n\neq 2k$ then we can avoid the case $'n=2k$, so we are done. The answers are 2 if n=2k and 1 otherwise

That one was also German TSTST #1.

Something interesting to think about: Let $k,m$ be positive integers. $A$ has a binary string $S$ of length $2k+1$ and writes down $m$ distinct binary strings that differ from $S$ by at most $k$ positions (this binary string may be identical to $S$). How large must $m$ be (in terms of $k$) such that $B$ is guaranteed to guess the binary string correctly in only 1 attempt? ($A$ may write the strings that makes it difficult for $B$ to guess.) In a sense, instead of using the full information of all the ${2k+1\choose k}$ strings, how much of these strings are actually necessary?

Call a pair of different binary strings of length $n$ $k$-friendly if the set of strings that differ in $k$ positions from one of them is the same as the set of strings that differ in $k$ positions from the other one. Notice that two strings are indistinguishable if and only if they are $k$-friendly. Claim. Pairs of $k$-friendly strings exist only if $n = 2k$. Moreover, for $n = 2k$, any two $k$-friendly strings differ in every position. To prove this, consider two $k$-friendly strings $X$ and $Y$. Let them be equal in $a$ positions and differ in $b$ positions. For each non-negative integer $r$ in the interval $[k - b, \min(a, k)]$ consider a string $S_r$ that differs from $X$ in $r$ of the positions where $X$ and $Y$ are equal and in $k - r$ of the positions where $X$ and $Y$ differ, and is equal to $X$ everywhere else. This is possible due to the interval where $r$ belongs. Then $S_r$ differs from $X$ in $k$ positions and thus also from $Y$. We then obtain $$r + b - (k - r) = k \implies 2k = 2r + b$$ This clearly cannot hold for more than one choice of $r$, as $k$ and $b$ are fixed. Assume that $b \leq k$, then we must have $k - b \geq \min(a, k)$. If $k \leq a$ this gives $b = 0$ and thus $X, Y$ are equal, which is impossible. Thus $a \leq k$ and $n = a + b \leq k$, which contradicts the conditions of the problem. Then $k \leq b$ which implies $k - b \leq 0$, and thus $r = 0$ is a valid choice. As this must be the only choice we obtain $\min(a, k) = 0$ and hence $a = 0$ as $k > 0$. Moreover applying the above equation with $r = 0$ we obtain $b = 2k$ which implies $n = 2k$ as $a = 0$. This completes the proof of the claim. This instantly implies that the contestant can guess in at most two attempts if $n = 2k$ and in at most one otherwise. As the strings composed of $2k$ zeroes and $2k$ ones are clearly $k$-friendly, two attemps are indeed necessary in the latter case.

What is the fastest algorithm for finding the optimal guess(es)? So far I have the following $\mathcal{O}(n\tbinom{n}{k})$ method in the case that $k\neq 0.5n$: Quote: Convert the strings on the board to a set of vectors $H\subset\mathbb R^n$ as in post# 3. Compute $c_H=\frac{1}{|H|}\sum_{s\in H}$. Explicitly write $c_H=(c_1,c_2,\dots,c_n)$. Define $u(x)$ to be $0$ if $x<0.5$ and $1$ if $x>0.5$, and likewise let $u(x)$ be $1$ if $x<0.5$ and $0$ if $x>0.5$. If $k<0.5n$, the leader's string will have its $i^\text{th}$ entry equal to $u(c_i)$. If $k>0.5n$, the leader's string will have its $i^\text{th}$ entry equal to $u'(c_i)$. There is also an $\mathcal{O}(n^3\tbinom{n}{k})$ algorithm for the case with $k=0.5n$: Quote: Choose some string and convert it to a vector $v_0\in\mathbb R^n$. One by one accumulate strings as vectors in $\mathbb R^n$ so that the set $v_1-v_0,v_2-v_0,\dots$ remains linearly independent (this may be checked with gaussian elimination in $\mathcal{O}(d^3)$ time where $d-1$ is the number of accumulated vectors.) Stop when we have $n$ vectors $v_0,v_1,\dots,v_{n-1}$. Overall, this is by far the rate-limiting step. Now replace $v_i$ with $v_i-v_0$ and save $v_0$ for later. Define $e_j(v_i)$ to be the $j^\text{th}$ entry of $v_i$. Fill the $(n-1)\times (n-1)$ matrix $A$ with entries $a_{ij}=e_{j}(v_i)$. Fill the vector $b\in\mathbb R^{n-1}$ so that $e_i(b)=-e_n(v_i)$. Solve $Ax=b$ with gaussian elimination. Construct $s\in\mathbb R^n$ satisfying $e_i(s)=e_i(x)$ for $1\leq i<n$ and $e_n(s)=1$. Use $s$ to create $s_1,s_2\in\mathbb R^n$ so that $e_i(s_1)=0.5+0.5e_i(x)$ and $e_i(s_2)=0.5-0.5e_i(x)$. We will need to guess both $s_1$ and $s_2$. One will be correct. The main obstacle to getting polynomial time in $n$ as $k$ varies is not having a faster way to find linearly independent sets. If this could be fixed, the algorithm would be much faster with only a slight modification...

We can WLOG the leader's original string is the 0 string (i.e. the string with all 0s), since we can compute everything else relative to it. Then the strings the deputy leader reveals are the permutations $P$ of $111\dots 100\dots 0$, where there are $k$ ones and $n-k$ zeroes. Suppose $S \neq 0, 1$ (= 111...1) differs from each of these $\binom{n}{k}$ strings in exactly $k$ positions. Since permuting the digits of $S$ doesn't change whether $S$ satisfies this condition (as permutations of strings in $P$ are also in $P$), we can assume $S$ starts with $1$ and ends with $0$. Then $S$ differs in exactly $k$ positions from $111\dots100\dots 0$ and $011\dots100\dots01$ (the first string starts with $k$ ones, and the second string is the first string, except transpose the first and last bits). This is clearly a contradiction, since $S$ differs in more positions in the second string. Thus $S = 0$ or $S = 1$. $S = 0$ is the original string. If $S = 1$ differs in $k$ positions from the strings in $P$, then clearly $n - k = k$, so $n = 2k$. Thus 2 guesses if $n = 2k$, 1 guess otherwise.

I'm still a bit unsure of the following: If $n=3\ne 2k$ and the string is $101$, and the deputy leader writes $001, 111, 100$, then are there two possibilities: 1) $k=1$, start string = $101$ 2) $k=2$, start string = $010$ But the answer states that if $n \ne 2k$, there is only $1$ guess needed?

In uraharakisuke_hsgs's solution, can someone explain what he meant by the k digits $b_j (j \neq i_t , t = \overline{1,k})$

Deputy leader has written $\dbinom{n}{k}$ strings and from these $\dbinom{n-1}{k} $ have the $i$'th number correct and $\dbinom{n-1}{k-1}$ wrong. Now , if $\dbinom{n-1}{k} $ , $\dbinom{n-1}{k-1}$ are different then the contestant can find the string in just $1$ try . If $\dbinom{n-1}{k-1}=\dbinom{n-1}{k} \Longleftrightarrow n=2k$ . In this case the contestant should look at first $k$ digits of all written numbers, and he can find exactly $2$ such that they are different in each digit. Let these two be $S_1$ and $S_2$ . One of $S_1,S_2$ has the first $k$ digits correct , wich means that the other has the last $k$ digits correct. In this case the contestant can find the string in $2$ tries because is impossible to tell wich of $S_1,S_2$ has the first digit correct. So ,the answer is $2$ if $n=2k$ and $1$ otherwise.

This problem is quite well suited for a C1, neither too difficult, nor too easy. 2016 IMOSL C1 wrote: The leader of an IMO team chooses positive integers $n$ and $k$ with $n > k$, and announces them to the deputy leader and a contestant. The leader then secretly tells the deputy leader an $n$-digit binary string, and the deputy leader writes down all $n$-digit binary strings which differ from the leader’s in exactly $k$ positions. (For example, if $n = 3$ and $k = 1$, and if the leader chooses $101$, the deputy leader would write down $001, 111$ and $100$.) The contestant is allowed to look at the strings written by the deputy leader and guess the leader’s string. What is the minimum number of guesses (in terms of $n$ and $k$) needed to guarantee the correct answer? ANSWER: $1$ if $n \neq 2k$ and $2$ if $n=2k$. SOLUTION: First consider the case when $n \neq 2k$. Choose a positive integer $i$ such that $i \leq n$. Take any of the $\binom{n}{k}$ binary strings. Then there are exactly $\binom{n-1}{k-1}$ strings which have the wrong digit at the $i^{\text{th}}$ position, and $\binom{n-1}{k}$ strings which have the correct digit at the $i^{\text{th}}$ position. As $n \neq 2k$, so $\binom{n-1}{k-1} \neq \binom{n-1}{k}$. Thus, we can easily find the leader's string by comparing the number of occurences of each bit at the $i^{\text{th}}$ position for all $i \in \{1,2, \dots ,n\}$. Now, suppose $n=2k$. WLOG assume that the leader's string consists of only $2k$ ones. Then the deputy leader's list consists of all binary numbers consisting of $k$ ones and $k$ zeros. However, in that case, had the leader chosen the zero string (consisting of $2k$ zeros), even then the deputy leader's list would have been the same. This means that the contestant will require at least two guesses to decipher the leader's string. We now show that two guesses actually suffice. Note that each string present in the deputy leader's list has its one's complement also present in that list. So make $\frac{1}{2} \binom{2k}{k}$ groups each consisting of two complementary binary strings. Select one group at random, and label its elements $\mathcal{B}$ and $\mathcal{B'}$. Then $\mathcal{B}$ will have ones at some $k$ positions, while $\mathcal{B'}$ will have zeros in exactly those positions. Color the digits at these positions red. Similarly, $\mathcal{B}$ will have zeros and $\mathcal{B'}$ will have ones in the remaining $k$ positions. Color the bits present here blue. Then the leader's string is either a mixture of the blue digits of $\mathcal{B}$ and the red digits of $\mathcal{B'}$, or vice versa. Thus, the contestant can find the leader's string in minimum two guesses. REMARK 1: In the case $n=2k$, showing the contestant just $\frac{1}{2} \binom{2k}{k}+1$ strings out of the deputy leader's list would also suffice (which is obvious by using PHP and our argument). Thus, the question could also have asked for the minimum number of strings which the contestant needs to be shown in order for him to guess the leader's string in minimum number of guesses. REMARK 2: Initially I started thinking that the contestant didn't know $n$ and $k$ (basically misread the problem ), which fortunately doesn't really affect the problem much. The contestant can easily figure out $n$ by finding the length of the strings in the deputy leader's list. While finding $k$, I used the fact that the number of strings in the deputy leader's list are equal to $\binom{n}{k}$. However, in this case, we encounter a small speed-breaker in that this gives the value $k$ as well as $n-k$ (unless $n=2k$). Thus, if $n$ and $k$ were not known to the contestant, then the answer would have been $2$ guesses for all possible values of $n$ and $k$.

We claim the answer is 1 if $n \not = 2k$ and 2 if $n=2k$. Arrange the given binary strings in a grid of bits, where the rows are each of the binary strings. Define the minority of column $i$ to be the bit 0 or 1 which appears strictly more times in the set of bits which contains the $i$'th position in each of the strings. Similarly define the majority of column $i$. We split into cases where (1) $n\not =2k$, (3) $n=2k$. Case 1: $n\not = 2k$. Assume $n>2k$. We claim we can deduce the answer immediately, and that the strategy is to take the string whose position $i$ is given by the majority of column $i$ of the grid. There are a total of $\tbinom{n}{k}$ strings we receive, and $\tbinom{n-1}{k-1}$ strings have a given position $i$ not the same as the $i$'th position of the answer, and $\tbinom{n-1}{k}$ strings with the $i$'th position same. It is easy to check that $n>2k\iff \tbinom{n-1}{k} > \tbinom{n-1}{k-1}$, which means that the majority of strings will have the $i$'th position same as the answer. Hence, this strategy us the correct answer. The case of $n<2k$ is very similar, except that we take the minority of the columns instead of majority (we are just changing the inequality sign). Case 2: $n=2k$. We claim that once we choose the first bit of our candidate answer, the rest of our answer is determined. Randomly choose the first bit. If this is the same as the first bit of the correct string, then the rest of the string has $n-1$ bits, and $k$ bits that are different from the answer. We know $n-1=2k-1\not =2k$, so now we take both the majority and minority of the remaining columns as per our previous strategy. Similarly, if the first bit we chose is not the same as the first bit of the correct string, then the rest of the string has $n-1$ bits and $k-1$ different bits, and $n-1=2k-1\not =2k-2$, so we take both the majority and minority of the remaining columns as per our previous strategy. Now we have 4 possible strings that can be the answer. But we can split these 4 strings into two pairs where the digits after the first are mirror images of each other (each digit is different), so we can go through the list and cross out exactly one in each of these pairs which will not work. Then, we are left with two possible strings, whose first digit is different. Each of these strings will produce the same lists, since they are mirror images of each other, so we need 2 guesses.

We claim that the contestant only need make one guess if $n \ne 2k$, and $2$ guesses otherwise. Without loss of generality, the leader of the IMO team selected the string of only $1$'s. Now, suppose that the contestant considers the possibility that the string of the leader of the IMO team is $a_1a_2\cdots a_n$, with each $a_i \in \{0, 1\}$. We will show that there cannot exist $a_i$ with $a_i = 0$ that work if $n \ne 2k$. Now, we observe that after considering all $\binom{n}{k}$ ways to change exactly $k$ members of this sequence, $a_i$ has probability $\frac{k}{n}$ of being $1$. In the $\binom{n}{k}$ strings that the deputy leader generates, each $b_i$ in the string $b_1b_2 \cdots b_n$ has probability $1 - \frac{k}{n}$ probability of being $1$. Thus, we must have that $1 - \frac{k}{n} = \frac{k}{n}$ for the contestant's hypothetical sequence with an $a_i = 0$ to possibly work, that is, $n = 2k$. Otherwise, we have exactly one possible sequence that the contestant will find that can work before he guesses, in this case, $111\cdots 1$. Now, suppose that $n = 2k$. We suppose there exist $i$ and $j$ with $1 \le i, j \le n$, $a_i = 0$, and $a_j = 1$. Consider a choice of $\binom{n}{k}$ members of this sequence to change such that $a_i$ gets changed but $a_j$ does not, which clearly must exist. Given that the contestant has not eliminated this sequence because it does not work, such a choice must leave exactly $k$ instances of $1$ in the sequence. Now, if we consider changing exactly the same members but changing $a_j$ instead of $a_i$, we see that we will end up with $k-2$ instances of $1$, absurd. Thus, a valid sequence in this case can only be $111\cdots 1$ or $000 \cdots 0$. Clearly, both of these sequences work, since in either case we will end up with all of the sequences with $k$ of them being a $1$.

For each digit, ${n-1\choose k-1}$ of the strings will have that digit out of place (because then there will be $k-1$ other digits out of place of the remaining $n-1$), and the other ${n\choose k}-{n-1\choose k-1}$ will have it in place. Thus the string can be found in 1 guess unless both these values are equal, in which case $n=2k$. In this case, the first digit must be randomly guessed, but after that it becomes a game with $n-1$ and $k-1$, which can be guessed in 1; so in this case 2 guesses are needed.

oops bad solution The answer is $1$ if $k \neq \tfrac{n}{2}$, and $2$ if $k = \tfrac{n}{2}$. For convenience, let us replace every of the deputy leader's strings with a string of n $a$s and $b$s, where $a$ corresponds to an unchanged digit and $b$ corresponds to a changed digit. First we consider $k = \tfrac{n}{2}$. Take any one of the deputy leader's strings, and we will try to identify which digits are bs. Consider taking any of the $\binom{n}{k}$ possible groups of k digits from the string. If the number of bs in there is between 1 and k-1, then we can rearrange the remaining $n-k$ as and bs to form another one of the deputy leader's strings that also has these k digits in the exact same places. However, is the number of bs is 0 or k, then we cannot rearrange the remaining $n-k = k$ as and bs. Thus if we inspect all possible $\binom{n}{k}$ groups, we can find a group that must be all as or all bs. Thus we can guess twice and guarantee a win. On the other hand, note that if the original string had all of its digits switched, then we would still get the same information from the deputy leader; thus 2 guesses is the best we can do. Now consider if $k < \tfrac{n}{2}$. Again, we will take any of the deputy leader's strings and try to identify the bs by considering taking any of the $\binom{n}{k}$ possible groups of k digits from the string. If the number of bs in there is between 0 and k-1, then we can rearrange the remaining $n-k$ as and bs (since there must be both as and bs, since we have $n-k > k$) to get another of the deputy leader's strings that overlaps with our group of k digits. If there are k bs, then we can't rearrange the remaining as and bs to get another of the deputy leader's strings. Thus if we inspect all possible $\binom{n}{k}$ groups, we can find a group that must be all bs, and we win. If $k > \tfrac{n}{2}$, then consider the string S formed by flipping all the digits in the original string. The deputy leader's strings all differ from S in exactly $n - k < \tfrac{n}{2}$ places; thus using the strategy for $k < \tfrac{n}{2}$ we can determine S and we win.

OTIS wrote: Titu selects two integers $n$ and $k$ with $n>k>0$, and announces them to Zuming and Po-Shen. Titu then secretly tells Zuming an $n$-digit binary string, and then Zuming writes down all $n$-digit binary strings which differ from Titu’s string in exactly $k$ places (hence writing exactly $\binom{n}{k}$ strings). Po-Shen then looks at the strings written by Zuming, and tries to guess the string that Titu originally selected. What is the minimum number of guesses (in terms of $n$ and $k$) needed to guarantee the correct answer? Above is the version I solved: We claim it will take two guesses if $n=2k$ and one otherwise. Assume $n \neq 2k$. Then, the first digit correctly appears $\binom{n-1}{k}$ out of the $\binom{n}{k}$, so we can distinguish the correct first digit. We use a similar process on the other digits. If $n=2k$, the string cannot be distinguished by the first digit, so it requires at least two guesses. On the other hand, we use the first two digits. If Titu's string has the same first and second digit, we will see $01$ and $10$ occur $\binom{2k-2}{k-1}$ times each, while $00$ and $11$ will occur $\binom{2k-2}{k}$ times each. So, Po can tell whether two digits in Titu's string are equal, meaning $2$ guesses can guarantee Titu's string.

16 ISL C1 wrote: The leader of an IMO team chooses positive integers $n$ and $k$ with $n > k$, and announces them to the deputy leader and a contestant. The leader then secretly tells the deputy leader an $n$-digit binary string, and the deputy leader writes down all $n$-digit binary strings which differ from the leader’s in exactly $k$ positions. (For example, if $n = 3$ and $k = 1$, and if the leader chooses $101$, the deputy leader would write down $001, 111$ and $100$.) The contestant is allowed to look at the strings written by the deputy leader and guess the leader’s string. What is the minimum number of guesses (in terms of $n$ and $k$) needed to guarantee the correct answer? Call the set of strings found by the deputy leader as the $\text{Cringe}$ of the binary word.Note that $\binom{n-1}{k}$ strings would be formed by keeping one digit constant and $\binom{n-1}{k-1}$ strings could be formed by changing the digit.So if $n \not = 2k$ then $\binom{n-1}{k-1} \not = \binom{n-1}{k-1}$ so the contestant will analyse a single position in all the strings and note down which digit occurs $\binom{n-1}{k}$ times ,this is itself the digit on this place and thus will find out the whole string $\square$ For $n \not = 2k$ : The answer is $\boxed{1}$ i.e. only one guess is sufficient. For $n=2k$ : We claim the answer is $2$ the proof follows 2 directions ;proving that we need atleast $2$ guesses and proving that $2$ actually works. Proof (forward direction) : We show that for $n=2k,2$ binary strings can have the same $\text{Cringe}$.Consider a string $110101$ and another string $001010$,note that these $2$ strings are formed by changing $0 \rightarrow 1$ from each other ($1\rightarrow 0,1 \rightarrow 0 ,0\rightarrow 1,1\rightarrow 0,0 \rightarrow 1,1\rightarrow 0$).We prove that if $n=2k$ these pairs of strings have the same $\text{cringe}$ however this is easy since if by reverting $k$ digits in one string we find a string,then if we revert the other $k$ digits(other $k$ positions) of the other string we get the same string and thus the proof is complete $\square$ Proving that $2$ actually works : Consider any $2$ digits note that we have only $4$ possibilities of finding them in the $\text{cringe}$ i.e. $\{10,01,11,00\}$.So note that; Number of strings in which Both of them are kept constant $=\binom{n-2}{k}=\binom{2k-2}{k}$ Both of them are reverted(changed) $=\binom{n-2}{k-2}=\binom{2k-2}{k-2}$ One of them are reverted and other is kept constant $=2\binom{2k-2}{k-1}$ Since the first $2$ values are equal by using the same analysis of part $1$ the contestant can find out if both the digits are same or different.So the student will compare the first digit with every other digit and thus will find out the whole string w.r.t the first digit.Since there are $2$ guesses for the first digit i.e. $0,1$,2 guesses are enought to find out the string $\square$ Hence we have found out the answer which is $$\boxed{1 \text{ if } n \not = 2k,2 \text{ if } n=2k} \text{ } \blacksquare$$

For each position of the secret string, the desired digit will appear exactly $\frac{n-k}{n}$ of the time. Hence if $n \ne 2k$, each digit can be extracted easily. Otherwise, consider the first $k$ digits in the case $n=2k$. Each string with exactly $m$ "preserved" digits from the first $k$ digits of the secret string will appear exactly $\binom km$ times. Thus the desired string will only appear once, while almost every other string appears more than once, so they can be eliminated as the choice for the starting $k$ digits and similarily the ending $k$ digits. The only issue is the "binary opposite" string with 0 preserved digits, which also appears only once. Indeed, the list of $\binom nk$ strings written down are the same for both the secret string and its opposite. Hence we must have 2 guesses, which gives our answer \[\boxed{\begin{cases} 1 & \quad \text{if } n \ne 2k \\ 2 & \quad \text{if } n = 2k \end{cases}}.\]

The answer is $2$ if $n = 2k$, and $1$ otherwise. Assume WLOG the leader is Titu, the deputy leader is Zuming, and the contestant is Po-Shen. Let Titu's binary string be $S = \overline{b_1b_2\cdots b_n}$, where each of the $b_i$ equals $0$ or $1$. Then for each $1 \le i \le n$, $\tbinom{n - 1}{k}$ of Zuming's strings have their $i$th digit equal to $b_i$, and the other $\tbinom{n - 1}{k - 1}$ strings have their $i$th digit equal to $1 - b_i$. If $n \ne 2k$, so that $\tbinom{n - 1}{k} \ne \tbinom{n - 1}{k - 1}$, then Po-Shen will be able to deduce all of the digits of $s$ simply by looking at each position, so he needs $1$ guess. Otherwise, Po-Shen will not be able to figure out the digits of Titu's string by simply looking at every position across all of Zuming's strings. Then I claim that in this case, there are $2$ possible strings. To prove this, let $s' \neq s$ be a string which produces the same $\tbinom{n}{k}$ strings from Zuming. Suppose that $s'$ differs from $s$ in $d > 0$ places. If $d = k$, then $s'$ is written down by Zuming which is obviously not possible. If $d < k$, then consider all of Zuming's strings which differ from $s$ in the same $d$ places that $s$ does; then these differ from $d$ in at most $k - d$ places, which poses a contradiction. If $d = n$, then in fact $s'$ will produce the same $\tbinom{n}{k}$ strings from Zuming (as the $k$ places which differed from $s$ for each string will now have the same digits as $s'$, and the $k$ places which were the same will now have different digits from $s'$). If $k < d < n$ then the same reasoning for when $ d < k$ works again. Hence there are $2$ possible strings that Titu could have written in this scenario (bitwise complements), and we are done.

For each digit, the number of correct values is ${n-1 \choose k}$ and the number of incorrect values is ${n-1 \choose k-1}$. If $n=2k$, then they are equal. If $n>2k$, then there are more correct values. If $n<2k$, then there are more correct values. As a result, if $n \neq 2k$, then only $1$ guess is needed. If $n=2k$, then note that if a binary string works, then the string with all its digits inverted also works. As a result, WLOG the last digit is $0$. Then, remove the last digit to everything. If the removed digit is $0$, then it becomes another problem but with $1$ less digit. If the removed digit is $1$, then it becomes another problem but with $1$ less digit and $1$ less swap. So there is $1$ possible value, but multiply by $2$ because the last digit could be $1$, so the answer is $2$.

If $n=2k$, then it takes $2$ moves. Otherwise $1$ move. We can recover each bit by making use of the fact that $\binom{n-1}{k} \neq \binom{n-1}{k-1}$ when $2k \neq n$. However when $n=2k$, the the produced list anyways has $2$ possible generators. So we do casework, and are able to get it in $2$ moves.

Note that we are given $\binom{n}{k}$ strings, consider one fixed position in each of them, by an easy counting we know that $\binom{n-1}{k}$ strings will have this digit in the right position and $\binom{n-1}{k-1}$ of them will have this digit changed, now if $n \ne 2k$ then since those two quantities are different we can easly differenciate them and thus re-construct the original string in only 1 guess. But if $n=2k$ then note that if we swap all the digits in the leader's binary string then after repeating the process we get that the deputy leader shares to the student the same list of binary strings as the string un-swapped, therefore, there is exactly 2 possible outcomes both correct from what the deputy leader gives to the student, and as a result the student is forced to make at least 2 guesses, now to achieve exactly 2 guesses just do the following, take all $k+1$ strings where the last $k-1$ digits remain fixed, and now we have two outcomes, one is assuming that those $k-1$ have all changed and that among the $k+1$ strings exactly one digit changes each time thus the student can guess one only string, on the other hand the student can assume that those $k-1$ digits never suffered a change and each time among those $k+1$ strings, $k$ strings change, giving a inverted string compared to your first choice, it is clear that by what we have seen, one of these two strings is correct so it takes at most 2 guesses. Therefore the minimun for $n \ne 2k$ is 1 and for $n=2k$ is 2 thus we are done .

We claim the answer is $1$ for $n \ne 2k$ and $2$ when $n = 2k$. $\textbf{Case 1: } n \ne 2k$ Note that among the $\binom{n}{k}$ strings, for each digit, it stays the same in $\binom{n - 1}{k}$ strings and toggles in $\binom{n - 1}{k - 1}$. Since $\binom{n - 1}{k} \ne \binom{n - 1}{k - 1}$, we can uniquely identify the digit in the original string by simply counting the number of instances of $0$s and $1$s. This yields $1$ as the minimum number of guesses. $\textbf{Case 2: } n = 2k$ First we show that we cannot get the correct answer in $1$ guess. Let $s$ be the chosen $n$-digit binary string, and let $s'$ be the string $s$ when all of its digits are toggled. We claim that both $s$ and $s'$ yield the same list, say $\ell$, of altered strings. This is easy to see: Given any alteration of $k$ digits on $s$, a unique equivalent alteration exists for $s'$ by simply toggling the other $k$ digits. We will now also show that $s$ and $s'$ are the only two strings that can generate this list $\ell$. By considering a constant binary vector shift, we can WLOG $s$ is the all-$0$ string and $s'$ is the all-$1$ string. But all strings in $\ell$ have precisely $k$ $0$s which is impossible to achieve with any other strings. Now to show that we can get the correct answer in at most $2$ attempts, simply take any binary string in the given list, and consider the $\binom{2k}{k}$ strings generated by toggling $k$ of its digits. (We are "reverse-engineering" the original string!) Then check all the strings in the list to see if any of them create the list. From our above claims, we get the correct answer in at most $2$ tries. We are done!

We claim the answer is $1$ if $n \neq 2k$ and $2$ otherwise. Case if $n = 2k$: For every string, the string formed by inverting each bit is present in the set, so by symmetry we require at least $2$ attempts. To prove that $2$ attempts is sufficient, consider the first half of the string. For each subset of $i$ bits of the first half, there are $\binom ki \binom{k}{k - i}$ strings with these $i$ bits inverted. There are thus only two distinct strings that have a unique first half, one of which that has all of the first half inverted and one with none. Thus it suffices to take the first half of all the strings and only note the two strings that have no matches in the list. Out of these, one is the correct string with the first half inverted and the second is the correct string with the second half inverted. We do not know which one. Invert the first half of both of these, then one of them is the correct answer. Case if $n \neq 2k$: For each bit, we can determine the inverted form appears $\binom{n - 1}{k - 1}$ times in the list and the correct form appears $\binom{n - 1}{k}$ times, and since these values are guaranteed to be distinct by $n \neq 2k$, we can uniquely determine each bit correctly on the first try.

The answer is $\boxed{1, n \neq 2k}$ and $\boxed{2, n = 2k}$ If $n \neq 2k$, then for each index of the string the correct one appears $\binom{n-1}{k}$ and the incorrect one appears $\binom{n-1}{k-1}$. Therefore the correct one can always be deduced. This argument fails however when $\binom{n-1}{k} = \binom{n-1}{k-1} \implies n = 2k$. In this case, clearly the string and its complement both work so we require two guesses. To achieve this, simply fix the first digit and use the same argument above on the rest of the string. For example consider $n=6, k=3$ with the string $101110$. If the first digit truly is $1$, then we know the first two digits are correct in $\binom{4}{3}$ ways but the first digit is correct and second digit incorrect in $\binom{4}{2}$ ways. Thus we can deduce the second digit and in a similar fashion the rest of the sting. The case where the first digit is incorrect gives the other case, so we are done.

First notice that the $n^{th}$ digit will be flipped in $$\binom{n-1}{k-1}$$of the given binary strings. So unless $$\binom{n-1}{k-1} = \frac{\binom{n}{k}}{2}\implies n=2k$$Po-Shen can directly find what each digit must be and in find the correct string in 1 guess. Now, suppose $n=2k$. Notice half the binary strings given will end in 0 and the other half in 1. Now, consider the remaining $n-1$ digits of each binary string. Assume that the last digit was flipped and became $x \in {0,1}$. Then, of first $n-1$ digits in the $\frac{\binom{n}{k}}{2}$ strings ending with $x$, we will have $k-1$ digits being flipped, which is identical to the case when Titu selects $n-1$ and $k-1$ and since clearly $n-1 \neq \frac{k-1}{2}$ the first $n-1$ digits can be determined in 1 guess. Thus, Po-Shen has to guess the last digit (with two options) requiring 2 guesses in total to hit the right answer.

Solved with a slight hint/being told that I was wrong. Obviously the number of strings written by deputy leader are $\binom{n}{k}$. For a particular place, the number of strings where it has the correct digit is $\binom{n-1}{k}$ so if the number of places it is written incorrectly is not equal to the number of places it is written correctly, then the contestant can uniquely determine all the places without leaving anything to chance. A quick calculation shows that this happens iff $n \neq 2k$. If $n=2k$, then fix any digit, say the foremost one, then if we fixed the correct digit, then we can instead view the case as being given a string of length $n-1$ and all the strings varying from this in $\frac{n}{2}$ places. Otherwise, we can view it as being given a string of length $n-1$ varying in $\frac{n-2}{2}$ places. In each of these cases, the contestant needs just one attempt, hence $2$ guesses are sufficient for the $n=2k$ case.

If $n\neq 2k$, then $1$ guess suffices. Specifically, Po-Shen can look at the $i$th bit across all $\binom{n}k$ strings written down. The original bit will appear $\binom{n-1}k$ times and the flipped bit will appear $\binom{n-1}{k-1}\neq\binom{n-1}k$ times as $n\neq 2k$. Hence Po-Shen can extract the $i$th bit of the original string for all $i$ and obtain the correct answer. If $n=2k$, then $2$ guesses is the minimum. Note that $2$ guesses are necessary as both Titu's original string and its complement, with all bits flipped, fit Zuming's description. On the other hand, if the first bit is determined, then Po-Shen can reduce the situation to one with $n'=2k-1$ by considering only the $\binom{n-1}k$ matching strings and throwing away the rest, extracting the other $n-1$ bits. $\blacksquare$