True And False

I suppose the True or False puzzle from last time has been up long enough, so I should probably get around to the solution. Like I said, my solution will basically be following the derivation that Tanya Khovanova did on her blog, because she did a better job of it than I expect to be able to anyway.

Alright, remember last time I said it is important to solve the simpler case of 5 questions with 4 attempts, so lets assume that we already have the ability to do that (I will show how later) and then use that to solve the problem of 30 questions. Without any loss of generality, we might as well have Victor answer "true" to all the questions first, to establish a base case. Next, we can submit the first 5 as "false" and the other 25 as "true" to get a base case for the first 5 questions (which we can then solve independently in 4 attempts), next we do the next batch of 5 as "false" with the rest "true" to get a base case for the next 5 and solve those in 4 more attempts. When we get to the last batch of 5, we don't need to do a final base case for those ones, as we already had our initial base case to tell us how many true answers are on the test in total, and we knew how many true were in each other block of 5, so we have already found our base for the last 5 questions. This argument shows quite generally that if you can do Q questions in N attempts then you can do MQ questions in MN attempts (for our case Q=5, N=4, M=6).

Now, how do we do 5 questions in 4 attempts? First we spend one attempt on our base case to see how many answers are "true", so we submit TTTTT. For the other 3 attempts, we will switch some of the answers to "false". There is no need to switch 3 of them to "false", as you get the same information by taking the compliment and switching the other 2 of them to "false". Similarly switching 4 or 5 to "false" is also meaningless, so we need only worry about 1 or 2. If we use FTTTT for our second attempt, we will get the answer to the first question and have 2 more attempts to solve out the remaining 4 questions, seems sort of hard (is in fact impossible, but I'm not going to prove that), so for our second attempt we must flip two answers to "false". Thus we can use FFTTT as our second test.

For our third test, we can basically choose between TTFFT ad FTFTT, depending on if we want our third attempt to have any overlap with our second attempt. But TTFFT is the same information as FFTTF which along with our second attempt gives the same information as TTTTF with only one "false" is probably a bad idea. Thus for our third attempt we should use FTFTT. By a similar logic we can use FTTFT for our fourth attempt.

So our exams are TTTTT, FFTTT, FTFTT, FTTFT. The first one give us the number of "true" answers. Adding up the second, third, and fourth mod 2, we can determine the answer to question 5 (as a "true" in one of the first four question contributes 0 mod 2, while a "false" contributes 1 mod 2). Next, going from TTTTT to FFTTT you either gained 2 points, lost 2 points, or stayed the same If you gained or last 2, you know the answers to the first two questions and finishing things off is easy, if you stayed the same then exactly one of the first two questions is true while the other is false. Similarly, TTTTT and FTFTT tells you if questions 1 and 3 are both true or false (easy to solve) or 1 of each. And same for questions 1 and 4. The only hard case is if your score never went up or down, but in that case exactly one of 1 and 2 is true, exactly one of 1 and 3 is true, and exactly one of 1 and 4 is true, thus the only cases are TFFF or FTTT and our base case will distinguish those.

This completes the proof that you can do 30 questions in 24 attempts. Note that this strategy was non-adaptive, in the sense that I never used the information gained from submitting one exam to decide my questions for the next exam. I could have just submitted my 24 exams in any order and then studied them to get my answers. One can in theory make more powerful strategies by using adaptive strategies, by using information you gain along the way to adjust what you are doing, but then the strategy tree is way harder to figure out, because it is theoretically very large.

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.