Bulls And Cows

I suspect that there might be only finitely many logic puzzles in the universe that I find interesting, because they seem to be running out at an alarming rate. Anyway, Tanya Khovanova had an interesting one a few weeks back that I might as well put here:
A test consists of 30 true or false questions. Victor will take the test but starts off having no idea what any answers are. After taking the test, Victor gets his score: the number of correct answers. He is allowed to re-take the same test several times. Can Victor work out a strategy that guarantees that he can figure out all the answers after the 24th attempt?

Note that Victor does not need to get everything right on the 24th attempt, just that he needs to know all the correct answers (so that on a 25th take, he would get them all right).

Naturally one can generalize this puzzle to Q questions and N attempts at the test. This game is actually just mastermind with two colours. One important simpler case is 5 questions, 4 attempts, I say that case is important because you can use it to solve this one of Q=30, N=24.

Tanya actually did a very nice explanation of the answer and some side calculations, when I post my answer I will basically just be copying what she wrote, but I like having an archive of stuff I find interesting, so I want this puzzle to be posted here.

No comments: