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: