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$?

  • 2
    Guess true for the first half and leave second half blank. If number of correct is greater than or equal to $4$, then for the final attempt use trues for the first half, else if number of correct is less than $4$ then use falses for the first half. For the second attempt, do the same thing for the second half of the questions. In the third attempt you use either all trues or all falses for the first half based on results of first attempt, all trues or all falses for second half based on results of first attempt. This gives an expected number of correct approximately $10.2$ with 3 guesses. – JMoravitz Nov 1 at 23:56
  • 1
    You can do similarly if you want to utilize four guesses instead of only three by breaking the test into thirds (as best you can, two sets of five and one set of six) which should give an expectation of about $10.8$. – JMoravitz Nov 2 at 0:00
  • Is that the best strategy? – user400359 Nov 2 at 0:01
  • It might be but probably not, but its certainly better than just knowing three answers for certain and guessing the rest. – JMoravitz Nov 2 at 0:03
  • That is true... – user400359 Nov 2 at 0:03

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}$.

  • Whoops, turns out JMoravitz has already suggested exactly this in comments. – Henning Makholm Nov 2 at 0:36
  • 3
    Right, but I don't expect that I could prove that it is optimal, especially since I'm technically in class supposed to be learning html and css right now and am distracted. cough – JMoravitz Nov 2 at 0:42

I don't know if these are optimal, but they're slightly better than the other answers. The general strategy is to start by guessing "True" for all questions on the first guess, as you suggested at the end of your question. The following guesses will subdivide the test into intervals, and in the final guess we can take the best of each interval (i.e., keep our guesses or flip them if fewer than half the interval were correct).

As an aside, you didn't specify the distribution of answers, so a malicious test-setter could try to foil us by choosing the answers in such a way as to make the algorithm give the worst possible result. But we can get around this simply by guessing randomly instead of "True"; for simplicity, then, let's just assume that the answers are independent and identically distributed.

Let's use $[a]$ to denote question $a$ and $[a,b]$ to denote questions $a$ through $b$. Also let $C_k$ be the number of correct guesses on the $k$th guess. By symmetry, we can assume that at least half the guesses in any interval are correct.

2 guesses allowed: $9.571$

The resulting information from the first guess is enough to let you get an expected score of $9.571$ on your second guess. This is already better than the four-guess strategy you proposed.

3 guesses allowed: $10.367$

If $C_1 = 16$, we get full points.

If $10 \le C_1 \le 15$, then use the next guess to look at only one question, $[1]$. We're guaranteed at least $C_1$ points; if we're lucky, we'll get $C_1+1$. (Lucky means we were wrong on $[1]$ and can therefore flip it to get one more point.)

On the other hand, if $C_1 = 8$ or $9$, then use the next guess to look at $[1,7]$. By the pigeonhole principle, this guarantees at least $4 + 5 = 9$ points; in fact, if you work out the possibilities, the expected number of points is $9.713$ and $9.885$ for $C_1 = 8$ and $C_1 = 9$ respectively.

4 guesses allowed: $11.086$

If $11 \le C_1 \le 15$, then guess $[1,2]$ next. If $C_2 = 1$, then we can guarantee one more point by guessing $[1]$; otherwise guess $[3]$.

If $C_1 = 10$, guess $[1,6]$ next.

If $C_1 = 9$, guess $[1,8]$ next.

If $C_1 = 8$, guess $[1,5]$ next.

I've skipped the details for these last three cases, but I can add them if you like. In short, a rule of thumb for the subsequent guesses would be to divide a large ambiguous interval in half when possible ("ambiguous" meaning that around half the answers were correct, so we don't have as much useful information as we would like and can't gain much from flipping our guesses).


Postscript: as far as I can tell, it is always beneficial to guess the whole set of questions first, as opposed to splitting them up into thirds, as in Henning Makholm / JMoravitz's answer. That being said, that strategy still performs well and has the benefit of being straightforward.

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

  1. 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.

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.