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?
Let’s assume that we have a more general problem. There are n questions, and a(n) is the smallest number of times we need to take the test to guarantee that we can figure out the answers. First we can try all combinations of answers. This way we are guaranteed to know all the answers after 2n attempts. The next idea is to start with a baseline test, for example, to say that all the answers are true. Then we change answers one by one to see if the score goes up or down. After changing n − 1 answers we will know the answers to the first n − 1 questions. Plus we know the total number of true answers, so we know the answers to all the questions. We just showed that a(n) ≤ n.
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:
saar:
a(5)=4
15 December 2011, 4:53 amhow 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)
saar:
soory, mistake, ther are 6^4 possibilities for the scores
15 December 2011, 9:06 amAnimesh:
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…
15 December 2011, 12:23 pmSo for a 3 question test it can be solved in 3 it’s more complicated but I guess similar logic can be applied.
saar:
to animesh
16 December 2011, 3:08 amsoory, 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?
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.
16 December 2011, 4:29 amsaar:
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?
16 December 2011, 7:30 amPaxinum:
This is just mastermind, with 2 colors where multiplicity is allowed.
17 December 2011, 6:45 amhttps://en.wikipedia.org/wiki/Mastermind_%28board_game%29
saar:
tanya, we are waiting to your answer, please hurry
18 December 2011, 1:30 amPseudonym:
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?
21 December 2011, 1:49 amPseudonym:
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:
21 December 2011, 7:06 pm0 → 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].
saar:
well, it seems good, but i need to check deeper.
22 December 2011, 1:21 amthanks very very much
saurav:
for the first part,
why is the minimunm numbers equal to n-1,
shouldnt it be n
24 December 2011, 5:49 amTanya 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 […]
2 January 2012, 8:09 pmAlejandro:
Hello, I lοg on tο yоur new stuff daily.
14 October 2012, 11:30 pmΥour humoristіc stуlе iѕ aωesome, kеep it uр!