## Binary Bulls without Cows

The following variation of a Bulls and Cows problem was given at the Fall 2008 Tournament of the Towns:

A test consists of 30 true or false questions. After the test (answering all 30 questions), Victor gets his score: the number of correct answers. Victor doesn’t know any answer, but is allowed to take the same test several times. Can Victor work out a strategy that guarantees that he can figure out all the answers after the 29th attempt? after the 24th attempt?

This is not enough to answer the warm-up question in the problem. We need something more subtle.

Let’s talk about the second part of the problem. As we know, 24 = 4 ⋅ 6. So to solve the second part, on average, we need to find five correct answers per four tests. Is it true that a(5) ≤ 4? If so, can we use it to show that a(30) ≤ 24?

The following three cases are the most fun to prove: a(5) = 4, a(8) ≤ 6, and a(30) ≤ 24. Try it!

By the way, K. Knop and L. Mednikov wrote a paper (available in Russian) where they proved that a(n) is not more than the smallest number k such that the total number of ones in the binary expansion of numbers from 1 to k is at least n − 1. Which means they proved that a(30) ≤ 16.

Share:

1. #### saar:

a(5)=4
how can it be? there are 32 possibities to the right answers, and just 24 possibities to the scores (each time, 0 to 5 right answers)

2. #### saar:

soory, mistake, ther are 6^4 possibilities for the scores

3. #### Animesh:

This one kept me thinking for a day…..my brain is rotting…i guess…

Anyway this is my solution, let’s consider a very simple case where correct answer is 0 1 0 (0 = F, 1 = T so it’s easy to consider….i luv numbers!)

if I try 0 0 0 I will get score 2 and automatically I know if I put 1 1 1 I will get score 3 – 2 = 1
next if I try 0 0 1 I will get score = 1 so I know 1 1 0 score = 2. This knowledge is enough for arriving at the solution.

Choose two solutions with same score, they are 0 0 0 and 1 1 0
Let’s say if the solution was 0 0 0 —> not possible coz then first one would have given result 3
next possibility = 0 0 1 —> again not possible coz it gives result
0 0 0 xor 0 0 1 = 1 1 0 or 2 1’s hence 2 correct answers
1 1 0 xor 0 0 1 = 0 0 0 or 0 0’s hence no correct answers

So we know 0 0 1 is not the solution,
if we try 1 0 0 then 0 0 0 xor 1 0 0 => 0 1 1 or 2 1’s
1 1 0 xor 1 0 0 = 1 0 1 or 2 1’s
so 1 0 0 can be a solution, similarly I find 0 1 0 can be a solution. There are no other possible solutions
1 0 0 & 0 1 0 can again be verified by the second solution set
Both 1 1 1 and 0 0 1 gives a score of 1. So without giving any more tests I know in 2 tests the solution is 0 1 0 or F T F.

If there is a more simplified one…do lemme know…
So for a 3 question test it can be solved in 3 it’s more complicated but I guess similar logic can be applied.

4. #### saar:

to animesh
soory, you are wrong. if the right anser is 100, u will have the same results, how do u know it is 010 and not 100?

5. #### Animesh:

@saar

Read again what I have written. I never say that correct answer is “0 1 0” I have just made an assumption. Can’t explain the strategy until I choose one of the solutions. The strategy is applicable to 1 0 0 also…..

Assuming if the solution is 1 0 0, the 0 0 0 will give score of 2 and so automatically I know 1 1 1 (previous one’s complement) will give a score of 1.

0 0 1 will give a score of 1 and so it’s comlement 1 1 0 will give a score of 2.

Using these results and then applying similar analysis I can zero in on the solution.

6. #### saar:

sorry, i did not understand. please exxplain again how do u know in 2 times which answer is right. uf u get the same results in the first and 2nd test’ how can we distugwish between the 2 opporunities?

7. #### Paxinum:

This is just mastermind, with 2 colors where multiplicity is allowed.
http://en.wikipedia.org/wiki/Mastermind_%28board_game%29

9. #### Pseudonym:

Quick information theoretic argument. You need to find n bits of information. Each attempt at the test gains you at most ⌈lg n⌉ bits of information (all logarithms are base 2). Therefore:

a(n) ≥ ⌈ n/⌈lg n⌉ ⌉

In particular:

a(5) ≥ 3
a(8) ≥ 4
a(30) ≥ 6

It may not be a terribly tight lower bound, but it’s a lower bound nonetheless.

Conjecture: For a test with n questions, if at each stage you are required to submit a test whose answers are consistent with all of the previous scores, you need to take the test n times to determine what all the answers are.

Now what if you had to submit all of your tests in advance, and so couldn’t use the results from a previous test to determine what answers to provide for the next test?

10. #### Pseudonym:

saar, here’s a strategy for n=5 laid out explicitly. The notation that I’m using is that a submission looks like [0,1,1,0,1] where 0 means answer “false” on this question and 1 means answer “true”.

This strategy is “optimal” in the following sense:

– The tree is minimal in the maximum depth of the tree (i.e. the number of trials required to know the answer).
– In the case of several trees that are optimal in the above property, it’s minimal in the average depth of the tree.
– In the case of several trees that are optimal in the above properties, submits a correct answer as often as possible.

I hope this formats correctly.

Try [0,0,0,0,0]. If the score is:
0 → The answer is [1,1,1,1,1].
1 → Try [0,0,0,1,1]. If the score is:
1 → Try [1,1,1,0,1]. If the score is:
3 → The answer is [1,1,1,1,0].
5 → The answer is [1,1,1,0,1].
3 → Try [0,1,1,1,1]. If the score is:
3 → Try [1,0,1,1,1]. If the score is:
3 → The answer is [1,1,0,1,1].
5 → The answer is [1,0,1,1,1].
5 → The answer is [0,1,1,1,1].
2 → Try [0,0,1,1,1]. If the score is:
1 → Try [1,1,0,0,1]. If the score is:
3 → Try [1,1,0,1,0]. If the score is:
3 → The answer is [1,1,1,0,0].
5 → The answer is [1,1,0,1,0].
5 → The answer is [1,1,0,0,1].
3 → Try [0,1,0,1,1]. If the score is:
1 → Try [1,0,1,0,1]. If the score is:
3 → The answer is [1,0,1,1,0].
5 → The answer is [1,0,1,0,1].
3 → Try [0,1,1,0,1]. If the score is:
1 → The answer is [1,0,0,1,1].
3 → The answer is [0,1,1,1,0].
5 → The answer is [0,1,1,0,1].
5 → The answer is [0,1,0,1,1].
5 → The answer is [0,0,1,1,1].
3 → Try [0,0,0,1,1]. If the score is:
1 → Try [0,1,1,0,0]. If the score is:
3 → Try [1,0,1,0,0]. If the score is:
3 → The answer is [1,1,0,0,0].
5 → The answer is [1,0,1,0,0].
5 → The answer is [0,1,1,0,0].
3 → Try [0,0,1,0,1]. If the score is:
1 → Try [0,1,0,1,0]. If the score is:
3 → The answer is [1,0,0,1,0].
5 → The answer is [0,1,0,1,0].
3 → Try [0,1,0,0,1]. If the score is:
1 → The answer is [0,0,1,1,0].
3 → The answer is [1,0,0,0,1].
5 → The answer is [0,1,0,0,1].
5 → The answer is [0,0,1,0,1].
5 → The answer is [0,0,0,1,1].
4 → Try [0,0,0,1,1]. If the score is:
2 → Try [0,0,1,0,0]. If the score is:
3 → Try [0,1,0,0,0]. If the score is:
3 → The answer is [1,0,0,0,0].
5 → The answer is [0,1,0,0,0].
5 → The answer is [0,0,1,0,0].
4 → Try [0,0,0,0,1]. If the score is:
3 → The answer is [0,0,0,1,0].
5 → The answer is [0,0,0,0,1].
5 → The answer is [0,0,0,0,0].

11. #### saar:

well, it seems good, but i need to check deeper.
thanks very very much

12. #### saurav:

for the first part,
why is the minimunm numbers equal to n-1,

shouldnt it be n

13. #### Tanya Khovanova’s Math Blog » Blog Archive » Binary Bulls Explained:

[…] recently posted an essay Binary Bulls without Cows with the following puzzle: The test Victor is taking consists of n “true” or […]

14. #### Alejandro:

Hello, I lοg on tο yоur new stuff daily.
Υour humoristіc stуlе iѕ aωesome, kеep it uр!