Binary Bulls Explained

I recently posted an essay Binary Bulls without Cows with the following puzzle:

The test Victor is taking consists of n “true” or “false” questions. In the beginning, Victor doesn’t know any answers, but he is allowed to take the same test several times. After completing the test each time, Victor gets his score — that is, the number of his correct answers. Victor uses the opportunity to re-try the test to figure out all the correct answers. We denote by a(n) the smallest numbers of times Victor needs to take the test to guarantee that he can figure out all the answers. Prove that a(30) ≤ 24, and a(8) ≤ 6.

There are two different types of strategies Victor can use to succeed. First, after each attempt he can use each score as feedback to prepare his answers for the next test. Such strategies are called adaptive. The other type of strategy is one that is called non-adaptive, and it is one in which he prepares answers for all the tests in advance, not knowing the intermediate scores.

Without loss of generality we can assume that in the first test, Victor answers “true” for all the questions. I will call this the base test.

I would like to describe my proof that a(30) ≤ 24. The inequality implies that on average five questions are resolved in four tries. Suppose we have already proven that a(5) = 4. From this, let us map out the 24 tests that guarantee that Victor will figure out the 30 correct answers.

As I mentioned earlier, the first test is the base test and Victor answers every question “true.” For the second test, he changes the first five answers to “false,” thus figuring out how many “true” answers are among the first five questions. This is equivalent to having a base test for the first five questions. We can resolve the first five questions in three more tests and proceed to the next group of five questions. We do not need the base test for the last five questions, because we can figure out the number of “true” answers among the last five from knowing the total score and knowing the answers for the previous groups of five. Thus we showed that a(mn) ≤ m a(n). In particular, a(5) = 4 implies a(30) ≤ 24.

Now I need to prove that a(5) = 4. I started with a leap of faith. I assumed that there is a non-adaptive strategy, that is, that Victor can arrange all four tests in advance. The first test is TTTTT, where I use T for “true” and F for “false.” Suppose for the next test I change one of the answers, say the first one. If after that I can figure out the remaining four answers in two tries, then that would mean that a(4) = 3. This would imply that a(28) ≤ 21 and, therefore, a(30) ≤ 23. If this were the case, the problem wouldn’t have asked me to prove that a(30) ≤ 24. By this meta reasoning I can conclude that a(4) ≠ 3, which is easy to check anyway. From this I deduced that all the other tests should differ from the base test in more than one answer. Changing one of the answers is equivalent to changing four answers, and changing two answers is equivalent to changing three answers. Hence, we can assume that all the other tests contain exactly two “false” answers. Without loss of generality, the second test is FFTTT.

Suppose for the third test, I choose both of my “false” answers from among the last three questions, for example, TTFFT. This third test gives us the exactly the same information as the test TTTTF, but I already explained that having only one “false” answer is a bad idea. Therefore, my next tests should overlap with my previous non-base tests by exactly one “false” answer. The third test, we can conclude, will be FTFTT. Also, there shouldn’t be any group of questions that Victor answers the same for every test. Indeed, if one of the answers in the group is “false” and another is “true,” Victor will not figure out which one is which. This uniquely identifies the last test as FTTFT.

So, if the four tests work they should be like this: TTTTT, FFTTT, FTFTT, FTTFT. Let me prove that these four tests indeed allow Victor to figure out all the answers. Summing up the results of the last three tests modulo 2, Victor will get the parity of the number of correct answers for the first four questions. As he knows the total number of correct answers, he can deduce the correct answer for the last question. After that he will know the number of correct answers for the first four questions and for every pair of them. I will leave it to my readers to finish the proof.

Knop and Mednikov in their paper proved the following lemma:

If there is a non-adaptive way to figure out a test with n questions by k tries, then there is a non-adaptive way to figure out a test with 2n + k − 1 questions by 2k tries.

Their proof goes like this. Let’s divide all questions into three non-overlapping groups A, B, and C that contain n, n, and k − 1 questions correspondingly. By our assumptions there is a non-adaptive way to figure out the answers for A or B using k tries. Let us denote subsets from A that we change to “false” for k − 1 non-base tests as A1, …, Ak-1. Similarly, we denote subsets from B as B1, …, Bk-1.

Our first test is the base test that consists of all “true” answers. For the second test we change the answers to A establishing how many “true” answers are in A. In addition we have k − 1 questions of type Sum: we switch answers to questions in Ai ∪ Bi ∪ Ci; and type Diff: we switch answers to (A ∖ Ai) ∪ Bi. The parity of the sum of “false” answers in A − Ai + Bi and Ai + Bi + Ci is the same as in A plus Ci. But we know A‘s score from the second test. Hence we can derive Ci. After that we have two equations with two unknowns and can derive the scores of Ai and Bi. From knowing the number of “true” answers in A and C, we can derive the same for B. Knowing A and Ai gives all the answers in A. Similarly for B. QED.

This lemma is powerful enough to answer the original puzzle. Indeed, a(2) = 2 implies a(5) ≤ 4, and a(3) = 3 implies a(8) ≤ 6.

Share:Facebooktwitterredditpinterestlinkedinmail

14 Comments

  1. Animesh:

    I am a bit confused with this argument
    “For the second test, he changes the first five answers to “false,” thus figuring out how many “true” answers are among the first five questions. This is equivalent to having a base test for the first five questions.”

    For example if the test is a 10 question test with answers T T F F T for first five and T F T F T for next five.

    as per ur logic I answer it as T T T….for all 10 questions as base case and I get a score of 6. Next if I do F F F…for first five and rest remain T’s I get a 5 as score.
    it’s like saying
    x + y = 6
    x + z = 5
    where x = number of correct answers from last 5 questions (which are common in both tests)
    y = number of correct answers in first five questions of the test 1
    z = number of correct answers in first five questions of the test 2
    all i can say is y – z = 1, so all i can figure out is that there is at least 1 question in first five questions which has answer “T”. I can’t figure out how many “T” answers are there in all for first five questions coz I don’t know the last five. Basically 6 can be obtained from 3 + 2 or 1 + 5 or something else. So I can’t seem to agree with your statement that using base test and the next one I will figure out how many “T” are there in first 5 questions…..

  2. Joseph:

    Animesh: you also know y + z = 5.

  3. Animesh:

    Oh ok!!!!!…..damn stupid of me….
    apologies for asking a stupid question…..

  4. Charles R Greathouse IV:

    Tanya, are you going to add this to the OEIS?

  5. Tanya Khovanova:

    Charles, please, go ahead and add it.

  6. Konstantin:

    Please, dont’t add it to OEIS: sequence a(n) is not defined well, and all our estimates is only upper bounds.

  7. Konstantin:

    Please, don’t add it to OEIS. Sequence a(n) is not defined well, and all our estimates is only upper bounds.

  8. Tanya Khovanova:

    Konstantin,

    The sequence is interesting in itself. The fact that it appeared in your paper and in my blog is more than enough motivation for submitting it.

  9. Konstantin:

    Oh, yes. I think, it was in article.
    https://oeis.org/A000788

    a(n) = A000788(n-1)+1

  10. Charles R Greathouse IV:

    Konstantin: How many terms are actually known? I wouldn’t add the bounds (except in comments), of course.

  11. Konstantin:

    Charles, our solutions and our approach were non-adaptive. So, no actually terms in original (adaptive) problem are not known. (May be, some small terms are known anf found “by hands”, but I don’t interesting it.)

  12. Alexey:

    Can you explain how this algorithm works with transition from 2 questions in 2 attempts to 5 questions in 4 attempts?
    I tried to do this myself and failed. Here is how I was thinking:
    For 2 questions A1=TF,B1=TF,AA1=FT,C1=T. So after TT,TT,T and TT,FF,F we will have TF,TF,T and FT,TF,? What should be in the last position for the last question? If we have T in the last position, then for questions 3 and 4, parity of the sum would be equal to parity of A, and if we have F in the last position, then parity of the sum will be equal to parity of A+1. None of this approaches gives us the value of C bit. Can you help me with this problem?
    Thank you.

  13. Tanya Khovanova:

    Alexey,

    For two questions the two tests are TT (base) and TF. A is the first two, B is the second two, C is the last question.

    Hence, for five questions.

    The first test is base: TTTTT.
    The second test establishing the base for A: FFTTT.
    The Sum test is: TFTFF.
    The Diff test is: FTTFT

    As you can see this is almost the same solution as I gave: you just need to reverse test 3.

  14. Alexey Vorobyov:

    Let me describe my difficulty on specific cases. Let’s take quizzes FFFFT and FFFTF. Our 4 attempts would result to 1,3,2,3 and 1,3,2,1 answers.
    So, described algorithm really provides different answers to different quizzes, but I don’t get the way we can find real answers to quiz from these numbers.
    From the first 2 questions we know that we have only one T and that both answers to A group are F.
    Now we got the answers to our ‘sum’ attempt which are 2 for both quizzes, and to our ‘diff’ attempt, which are 3 and 1.
    You say: The parity of the sum of “false” answers in A − Ai + Bi and Ai + Bi + Ci is the same as in A plus Ci. But we know A’s score from the second test. Hence we can derive Ci.
    And here is where I have a difficulty to follow. For FFFFT quiz where C=T we get an odd sum (2+3) and for FFFTF case where C=F we get an odd sum (2+1). So, how can you derive from the parity of the sum (3 and 5 in our cases) the value of Ci bit?
    Than you.

Leave a comment