What is the optimal way to take $16$ question true/false test with four attempts?

Question

Question:

Suppose a student is taking a $16$-question true/false test with four attempts. They must keep the store that they obtain after the fourth trial.

He or she does not know the answer to any question. After the test is completed, the grader tells you how many you got correct but not which ones.

What's the best way to maximize the expected value of the fourth attempt?

---

My thoughts:

So, to clarify the question, one way to make the expected value equal to $9.5$ is as follows:

Attempt 1: Answer question $1$ and leave the rest blank. If the grader tells you that you got $1$ right, you know the answer to question $1$ with certainty. If the grader tells you that you got $0$ correct, then you still know the question to $1$ with certainty (if you put true, then it will be false).

Attempt 2: Repeat with question 2.

Attempt 3: Repeat with question 3.

So, we're guaranteed three questions right, and the expected value for attempt four is $3 + \sum_{i=1}^{13}1 \cdot 1/2 = 3 + 6.5 = 9.5$. So we're expected to get $9.5$ right.

---

Another thing that someone could do is answer "TRUE" for every question on attempt $1$. That'll tell you how many true/false questions there are in total. Then, on the second attempt, leave the second half of the test blank, and answer TRUE for everything in the first half. This is sort of like a binary search. It tells you how many are true in the first half, and in the first quarter, etc.

I didn't get anywhere with this.

Is my solution of an expected value of $9.5$ the most optimal solution? What if there were $3$ attempts instead of $4$?

Answer 1

Here is one strategy that beats yours:

Attempt 1: Give random answers to questions 1-5 and leave the rest blank.

Attempt 2: Give random answers to questions 6-10 and leave the rest blank.

Attempt 3: Give random answers to questions 11-15 and leave the rest blank.

Final test: For questions 1-5 give the same answers as in attempt 1, except invert all of them if you had less than 3 correct. Similarly for 6-10 and 11-15. Answer question 16 randomly.

This guarantees you at least 3 correct answers in each group of 5, and some probability of even more. If I'm calculating correctly the expected number of rights in each group is $3\frac{7}{16}$, for a total expectation of $3\cdot 3\frac{7}{16} + \frac12 = 10\frac{13}{16}$.

Answer 2

My 2 cents on the problem.

1. Divide the problems into sections where you want to guess.
2. If previous guess did not yield much information (high variance results which would let us get the most right), include that guess into this batch of guesses.

So here's how I would tackle it. 1. Guess all T on 1-5. If we get 0, 1, 4, or 5 then leave blank on next guess because we will get at least 4/5 correct on this section ( although if you really want, include getting 4 or 1 correct in the next guess ). However if we get 3 correct then

2. Guess TTTFF on problems 1-5, guess all T on 6-10.

You now have a .3% chance to get all 10 right, a 1.6% chance to get 9 right, a 5% chance to get 8 right, a 12.5% chance to get 7 right, a 21.2% chance to get 6 right, a 23.8% chance to get 5 right, a 18.8% chance to get 4 right, a 11.2% chance to get 3 right, a 4.7% chance to get 2 right, a .9% chance to get 1 right.

Now from this distribution we have some good information from our previous guess on 1-5 and this current guess too. If we get 10 right, we know all 1-10.

If we get 9 right, we know for sure that we got the first 5 right and 4/5 right in 6-10.

If we get 8 right, then the conditional probability TTTFF is the answer to the first 5 is (1/10*10/32)/(1/10*10/32+1/32*6/10) = 63%.

IF we get 7 right, the conditional probability we got the first 5 right is only 25%, while 75% chance we got 4/5 right on 6-10 and got 3 right on 1-5.

Pretty much a similar strategy as others posted earlier with just splitting into 3 sections and flipping but always trying to maximize information by analyzing the conditional probability distribution. This should get a higher expected value.