Guess the leader's binary string!

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

510 posts

#1 h Jul 19, 2017, 4:31 PM • 13 Y

Y by Davi-8191, tenplusten, MathbugAOPS, Welp..., OlympusHero, mathleticguyyy, centslordm, jhu08, iker_tz, Adventure10, lian_the_noob12, RandomPerson11, NicoN9

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?

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

math163

58 posts

math163

#2 h Jul 19, 2017, 4:39 PM • 6 Y

Y by reveryu, Lemon293, jhu08, Adventure10, Mango247, jkim0656

(redacted)

This post has been edited 5 times. Last edited by math163, Nov 10, 2018, 8:24 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

rafayaashary1

2541 posts

rafayaashary1

#3 h Jul 19, 2017, 4:40 PM • 14 Y

Y by Wave-Particle, Problem_Penetrator, Ankoganit, opptoinfinity, aops29, Lioghte24, jhu08, Pranav1056, 407420, caicasso, Adventure10, Mango247, thesnakeinthebox, MS_asdfgzxcvb

Geometric Solution

This post has been edited 4 times. Last edited by rafayaashary1, Jul 25, 2017, 6:48 PM
Reason: reformatted for legibility :)

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

uraharakisuke_hsgs

365 posts

uraharakisuke_hsgs

#4 h Jul 20, 2017, 6:22 PM • 3 Y

Y by jhu08, Adventure10, Mango247

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

This post has been edited 2 times. Last edited by uraharakisuke_hsgs, Jul 20, 2017, 6:23 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

rmtf1111

698 posts

rmtf1111

#5 h Jul 20, 2017, 6:31 PM • 5 Y

Y by vsathiam, MathbugAOPS, jhu08, Adventure10, Mango247

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

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Kezer

986 posts

Kezer

#6 h Jul 22, 2017, 9:48 AM • 2 Y

Y by Adventure10, Mango247

That one was also German TSTST #1.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

anything--

11 posts

anything--

#8 h Jul 25, 2017, 12:35 PM • 1 Y

Y by Adventure10

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?

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

juckter

322 posts

juckter

#9 h Jul 25, 2017, 3:10 PM • 2 Y

Y by Adventure10, Mango247

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

rafayaashary1

2541 posts

rafayaashary1

#11 h Jul 26, 2017, 12:18 AM • 2 Y

Y by Adventure10, Mango247

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...

This post has been edited 2 times. Last edited by rafayaashary1, Jul 26, 2017, 2:23 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

suli

1498 posts

suli

#12 h Jul 26, 2017, 12:35 AM • 2 Y

Y by Adventure10, Mango247

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

ComboMan

4 posts

ComboMan

#14 h Sep 1, 2018, 4:26 AM • 2 Y

Y by Adventure10, Mango247

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?

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Plops

946 posts

Plops

#15 h Nov 15, 2018, 4:43 AM • 1 Y

Y by Adventure10

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})$

This post has been edited 3 times. Last edited by Plops, Nov 15, 2018, 4:46 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

XbenX

590 posts

XbenX

#16 h Jan 12, 2019, 7:27 PM • 3 Y

Y by VicKmath7, Adventure10, Mango247

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Vrangr

1600 posts

Vrangr

#17 h Jan 18, 2019, 12:59 PM • 4 Y

Y by AlastorMoody, Supermathlet_04, Adventure10, Mango247

Solution

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

math_pi_rate

1218 posts

math_pi_rate

#18 h Jan 19, 2019, 3:28 PM • 3 Y

Y by Adventure10, Mango247, EvansGressfield

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$ .

This post has been edited 5 times. Last edited by math_pi_rate, Jan 19, 2019, 3:48 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

eibc

598 posts

eibc

#68 h Dec 27, 2023, 3:13 AM • 2 Y

Y by Sagnik123Biswas, RaymondZhu

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

ryanbear

1055 posts

ryanbear

#69 h Mar 1, 2024, 4:34 AM

Y by

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$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Sagnik123Biswas

419 posts

Sagnik123Biswas

#70 h May 8, 2024, 8:54 AM

Y by

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

MathLuis

1471 posts

MathLuis

#71 h Jun 30, 2024, 5:29 PM

Y by

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 :cool:

.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

blueprimes

324 posts

blueprimes

#72 h Aug 9, 2024, 1:30 AM

Y by

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, just generate the list over all strings and see what works. By our above claim, we get it in at most $2$ tries.

We are done!

This post has been edited 1 time. Last edited by blueprimes, Feb 18, 2025, 6:43 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

ezpotd

1251 posts

ezpotd

#73 h Sep 18, 2024, 3:32 AM

Y by

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

lpieleanu

2853 posts

lpieleanu

#74 h Nov 29, 2024, 5:41 PM

Y by

Solution

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

eg4334

617 posts

eg4334

#75 h Dec 10, 2024, 12:59 AM

Y by

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.

This post has been edited 1 time. Last edited by eg4334, Dec 10, 2024, 1:33 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

cursed_tangent1434

565 posts

cursed_tangent1434

#76 h Dec 22, 2024, 9:51 AM

Y by

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Eka01

204 posts

Eka01

#77 h Dec 28, 2024, 7:43 PM

Y by

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.

This post has been edited 1 time. Last edited by Eka01, Dec 28, 2024, 7:44 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

smileapple

1010 posts

smileapple

#78 h Dec 29, 2024, 7:55 AM

Y by

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$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

NTguy

23 posts

NTguy

#79 h Feb 13, 2025, 9:16 AM • 1 Y

Y by alexanderhamilton124

Very cool problem, there are $\binom{n}{k}$ total strings, and in $\binom{n-1}{k-1}$ of them, a particular digit will have been changed. So, for each digit we need to count the number of strings where it is $0$ and $1$ . Whichever of $0$ and $1$ comes $\binom{n}{k} - \binom{n-1}{k-1}$ times is the correct digit. The only problem arises when $\binom{n}{k} = 2\cdot \binom{n-1}{k-1}$ which is true iff $n=2k$ . For this case, first assume the first digit in the leader's string is $1$ . Then, in the $\binom{n-1}{k-1}$ strings which have $0$ as the first digit, we know that the first digit has changed, leaving an $n-1$ digit number with $k-1$ digits changed. This is the same as the case of $n \neq 2k$ . So, from this we can deduce the entire string and guess it. If it is wrong, we know that the first digit is $0$ , and repeat this process. So, for $n=2k$ we require $2$ guesses and for $n \neq 2k$ we require only $1$ guess.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

alexanderhamilton124

383 posts

alexanderhamilton124

#80 h Feb 15, 2025, 8:28 PM • 1 Y

Y by L13832

For $n$ odd, and for $n$ even and $k \neq \frac{n}{2}$ , the answer is $1$ . Consider any digit place. The right digit occurs $\binom{n - 1}{k}$ times in this place, and the wrong one appears $\binom{n - 1}{k - 1}$ . These two are clearly not equal for this case, so the contestant simply picks the one that apears $\binom{n - 1}{k}$ times for each digit, which gives us one guess.

For $n = 2k$ , we can't do it in one guess. This is because if the leader gives the string which is different from this string in all places, we get the same set of strings. We now prove we can do it in two guesses. Randomly pick the first digit. Consider a digit place. The right digit will appear $\binom{n - 2}{k}$ times and the wrong one will appear $\binom{n - 2}{k - 1}$ times (even if the first digit is wrong, the digits in this place will have the same number of occurrences in the reverse order). These two aren't equal since $n - 2$ is even, so pick the one that appears $\binom{n - 2}{k}$ times for each digit place. Give this as the answer. If it's wrong, that means we picked the first digit wrong and then simply do this with the second digit.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Maximilian113

521 posts

Maximilian113

#81 h Feb 23, 2025, 3:13 AM

Y by

Note that swapping $k$ with $n-k$ and vice versa yield equivalent cases, so WLOG assume that $k \leq \frac{n}{2}.$

If $n \neq 2k,$ we have $2k < n.$ Therefore there are multiple pairs of strings that differ at $2k$ places, those places must be where a bit flipped. Therefore in the other positions the bits must not have changed, therefore we can determine them. And, since we have all $\binom{n}{k}$ strings it follows that we can use this method to uniquely determine the original string, so $\boxed{1}$ guess.

If $n = 2k,$ we can look at pairs of strings that differ by $n-2$ places. Then, for the other $2$ places, one of them must have been changed twice, while the other one has to have been original. Therefore if we fix the first digit, taking all pairs of such strings and analyzing the pairs of unchanged bits allows us to determine the string. Hence we have at most $\boxed{2}$ possibilites as there were $2$ possibilites for the first digit.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

de-Kirschbaum

187 posts

de-Kirschbaum

#82 h Mar 30, 2025, 5:38 PM

Y by

We claim that the contestant can guess it in $1$ if $k \neq \frac{n}{2}$ and $2$ if $k=\frac{n}{2}$ .

If $k \neq \frac{n}{2}$ then we know that each digit will be flipped $\binom{n-1}{k-1}$ times and be correct $\binom{n}{k}-\binom{n-1}{k-1}=\binom{n-1}{n-k-1} \neq \binom{n-1}{k-1}$ times. Thus at each digit the contestant can look at all of the binary strings written and pick the digit that appears $\binom{n-1}{n-k-1}$ times and that gives them the correct bit.

If $k=\frac{n}{2}$ then we know that $\binom{n-1}{n-k-1}=\binom{n-1}{k-1}$ so the contestant can no longer pick the correct digit just by looking at the number of times they appear. However, the contestant can guess the first bit to be $1$ or $0$ (unflipped) and then assume the rest of the $n-1$ bits are flipped in $\frac{n}{2}$ places, then following the strategy in the previous case the contestant can guess a number according to that. If the first bit was guessed correctly, then the contestant will recover the original string following this method because then obviously all the flips must happen in the $n-1$ bits. If the first bit was guessed incorrectly, the contestant will recover the complement of the original string, but either way since the first bit is either $1$ or $0$ it takes two guesses to guarantee the original string.

Z K Y