Solving yes-no test

Question

There is a test with N YES or NO questions. You can write the test and the professor will tell you how many of your answers are correct. What is the fastest way to pass the test? I.e. give correct answers to all questions with the minimum number of trials.

UPD The solution with N+1 trials is obvious. On each trial we will have correct answer to a single question. It is 1 bit of information. But professor gives us a number from 0 to N each time, it is log₂(N + 1) bits of information. That's why the best solution has O(N / log(N)) complexity. I'm looking for any solution with sub-linear worst time complexity.

Answer 1

The obvious improvement over the N+1 solution:

Start with all Y answers.

Then we know exactly how much yes/no there are.

Let p be the probability of having yes on any given position. p >= 1/2 without loss of generality.

Then I will reveal two first answers in average of 2 - p^2 tries.

I change my answer for the two first questions. At least p^2 of the time I will know the exact answer for both of them. If not - then I at least know that one of them is Y and the other is N and I need to ask one more question.

So in the worst case of p = 1/2 I need 1 + N * 7/8.

Answer 2

In the article from Carsten's comment, Erdös and Rényi show an example of how the problem can be formulated as finding the smallest number of test sequences that together can generate a unique hash for the unknown sequence. Since their example shows a sequence five digits long solved with four tests, I tried to come up with a sub-linear number of tests for sequences of length six and seven.

Looking at Erdös and Rényi's example and inspired by Ioannis' mention of "divide and conquer," I thought perhaps the test sequences kind of divide and then subdivide the sequence. It took a few tries to get working tests for sequence length seven.

Perhaps one way to think about the algorithm you are asking for could be a way to generalize / automate the generation of these test sequences.

The JavaScript program below compares test-sequences against all sequences of a given length, hashing the number of coinciding digits. If two different sequences generate the same hash, the program notifies that a match was found, meaning this combination of tests would not work. If no match was found, it means the hashes are unique and the tests ought to work.

// http://resnet.uoregon.edu/~gurney_j/jmpc/bitwise.html
function setBits(i)
{
     i = i - ((i >> 1) & 0x55555555);
     i = (i & 0x33333333) + ((i >> 2) & 0x33333333);
     return (((i + (i >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24;
}

// http://stackoverflow.com/questions/10073699/pad-a-number-with-leading-zeros-in-javascript
function pad(n, width, z) {
  z = z || '0';
  n = n + '';
  return n.length >= width ? n : new Array(width - n.length + 1).join(z) + n;
}

function numCoincidences(a,b){
    var n = 0
    for (var i=0; i<a.length; i++){
        if (a.charAt(i) == b.charAt(i)){
            n ++
        }
    }
    return n
}

var sequenceLength = 6

var tests = [
        "111111",
        "111000",
        "010010",
        "011001",
        "000100"
    ]

/***
var sequenceLength = 7

var tests = [
    "1111111",
    "1111000",
    "0100100",
    "0110010",
    "0110001",
    "0001000"
]
***/

var hash = {}

console.log("       " + tests.join(" "))

for (var i=0; i<1<<sequenceLength; i++){
    if (setBits(i) < Math.floor(sequenceLength / 2)){
      var tmp = pad(i.toString(2),sequenceLength)
      var h = ""
      for (var j in tests){
        h += numCoincidences(tests[j],tmp)
      }
      console.log(tmp + "   " + h.split("").join("      "))
      if (hash[h]){
          console.log("found match")
      } else {
          hash[h] = true
      }

    }
}

console.log("done")

Output:

"       111111 111000 010010 011001 000100" <-- test sequences
"000000   0      3      4      3      5"
"000001   1      2      3      4      4"    <-- sequences to match, followed by
"000010   1      2      5      2      4"             the number of coincidences 
"000011   2      1      4      3      3" 
"000100   1      2      3      2      6" 
"000101   2      1      2      3      5" 
"000110   2      1      4      1      5" 
"000111   3      0      3      2      4" 
"001000   1      4      3      4      4" 
"001001   2      3      2      5      3" 
"001010   2      3      4      3      3" 
"001011   3      2      3      4      2" 
"001100   2      3      2      3      5" 
"001101   3      2      1      4      4" 
"001110   3      2      3      2      4" 
"010000   1      4      5      4      4" 
"010001   2      3      4      5      3" 
"010010   2      3      6      3      3" 
"010011   3      2      5      4      2" 
"010100   2      3      4      3      5" 
"010101   3      2      3      4      4" 
"010110   3      2      5      2      4" 
"011000   2      5      4      5      3" 
"011001   3      4      3      6      2" 
"011010   3      4      5      4      2" 
"011100   3      4      3      4      4" 
"100000   1      4      3      2      4" 
"100001   2      3      2      3      3" 
"100010   2      3      4      1      3" 
"100011   3      2      3      2      2" 
"100100   2      3      2      1      5" 
"100101   3      2      1      2      4" 
"100110   3      2      3      0      4" 
"101000   2      5      2      3      3" 
"101001   3      4      1      4      2" 
"101010   3      4      3      2      2" 
"101100   3      4      1      2      4" 
"110000   2      5      4      3      3" 
"110001   3      4      3      4      2" 
"110010   3      4      5      2      2" 
"110100   3      4      3      2      4" 
"111000   3      6      3      4      2" 
"done"