------------------------------------------------- ------------------------------------------------- Here is my response to Ryohei Miyadera’s Test Taking Strategy puzzle: The ‘best’ strategy depends on the requirements of the student in question and there are several alternative measures that can be applied. By exhaustive enumeration of all 144 valid test sequences, I have obtained the following optimal strategies, their relevant scores, and the list of guesses that achieve that score: MAXIMUM AVERAGE SCORE: 6.36111 T T F T T T T T F T T MAXIMUM WORST CASE SCORE: 6 T T T T T T T T T T T MAXIMUM BEST CASE SCORE: 11 Any valid sequence (no three in a row and at least 6 ‘correct’s) such as T T F T F F T T F T T MAXIMUM CHANCE OF ATTAINING A MINIMUM SCORE OF: AT LEAST 6 144 in 144 T T T T T T T T T T T (Average = 6.2222) AT LEAST 7 77 in 144 T T T T T T T T F T T (Average = 6.2917) T T F T T T T T T T T (Average = 6.2917) AT LEAST 8 48 in 144 T T F T T F T F F T T (Average = 6.1806) T T F F T F T T F T T (Average = 6.1806) AT LEAST 9 30 in 144 T T F T T F T T F T T (Average = 6.3333) AT LEAST 10 9 in 144 T T F T T F T T F T T (Average = 6.3333) AT LEAST 11 1 in 144 T T F T T F T T F T T (Average = 6.3333) NOTE: These above strategies also represent one of several optimal percentile strategies. ‘At least 6’ gives optimal strategy for maximising between 144 and 78 wrong (i.e. 0 to 45.833th percentile), ‘At least 7’ maximises between 77 and 49 wrong (i.e. 46.5278th to 65.9722th percentile), etc MAXIMUM MEDIAN SCORE: 7 T T T T T T T T F T T T T T T T F F T F T T T T F T T T T T T T T T T F T T T T T F F T T T F T T T T F F T T T T F T T T F T F T T T T F T T F T T F T T T T F T F T T T F T T T T F T F F T T T T T T T F T F F T F F T T T T F F T T T T F T T T T F F T F F T F T T T F F T T T T T F T T MAXIMUM LIKELY (MODE) SCORE: 7 T T T T T T T T F T T T T T T T T F T F F T T T T T T F T F F T T T T T T T F F T F T T T T T T F F T F T T T T T T T F F T F F T F T T T F T F F T T T T T T T F T F F T F F T T T F T T T T T T T T T T F T T T T T F F T T T F T T T T F F T T T T F T T F T T F T T T T F T T F T F T T T T T F T F F T T T T T T T F T F F T T F F T T T F T F F T F T F T T T F T F F T F F T T T T F F T T F T F F T T T F F T F T T T T T T T F F T F T T F F T T T F F T F T F F T T T T F F T F F T F T T T F T F T F F T F T T T F F T T T T T F T T T F F T T F T F F T T T F F T F T T T T T T T F F T F T T F F T T T F F T F F T F T T T T F F T F F T F F F T T F F F T F F T F F T F T F F T F F T T T T Corey Plover ------------------------------------------------- Ryohei Miyadera -- A teacher is going to give students a test. The test consists of 11 questions and along with each question there is an answer. The answer may be correct or false. The students are expected to write "correct" if they think the answer is correct and "false" if they think it false. The teacher has two habits. One is that he never present three correct answers in a row nor three false answers in a row. Another one is that he presents more correct ones than false ones. What is the best strategy for students if they do not know anything about the subject? Well, there are only 2048 possible submissions for an 11-question true-false test, and half of them are negated by the "more than half true" rule. "No three consecutive answers the same" knocks out a bunch more. A computer search reveals 144 possible solution sets. Of these, only 67 have question 3 true, and only 67 have question 9 true. All the others are true more than half the time. For the best average score, you should answer these two false and the rest true. But this average score is still only about 6.4 questions right, less than 1 better than random guessing in the absence of knowledge of the teacher's habits in test-writing. A student might have other strategies, depending on the grading system, such as trying to have the best chance of reaching a certain score, which can be optimized by trying each of the 2048 possible submissions against each of the 144 possible answer sets and finding which one succeeds most often. Joseph DeVincentis ------------------------------------------------- Answer A quick search (using Mathematica) produces 144 0-1-sequences of length 11 having the required properties. Only 67 of these sequences have a 1 at position 3, and the same is the case for position 9. At all other positions more than half of the sequences have a 1. So, assuming that all allowed sequences are equiprobable, the best strategy would be to write "False" at positions 3 and 9 and "Correct" at all other positions. Christian Blatter ------------------------------------------------- I'm not sure if I am entirely correct, but here goes: There are 2048 possible unrestricted ways to devise the 11-question true/false test. Of those 2048 permutations, only 144 are possible under the restrictions that no three questions in a row are all true or all false, and that there are more true answers than false. Looking strictly at each question, assuming all 144 permutations are equally likely, the likelihood that any question is true is broken down as follows: Question 1: 68.1% Question 2: 57.6% Question 3: 46.5% Question 4: 57.6% Question 5: 55.6% Question 6: 51.4% Question 7: 55.6% Question 8: 57.6% Question 9: 46.5% Question 10: 57.6% Question 11: 68.1% Only questions 3 & 9 are more likely to be false than true. Therefore, the best string of answers is TTFTTTTTFTT, which gives an expected value of 6.361. Answering all questions true would seem at first glance to be the obvious answer, since the test taker is guaranteed to score at least a 6, but the expected value of this string is 6.222, less than the value of TTFTTTTTFTT. Alan Lemm ------------------------------------------------- It depends on what is your desired outcome Ø Being risk averse, I would just answer all questions as ‘correct’. That way, I am certain to pass and, if the teacher chooses randomly from amongst the 144 possible answer sequences, my average mark will be 6.222. This has the disadvantage of showing one’s hand, so he would likely adopt a different strategy next time. Ø Another option is to answer ‘false’ for questions 3, 6 and 9, with ‘correct’ for the other questions (which all have ‘correct’ as the proper answer more than half the time). This raises the average mark to 6.333, but reduces the chance of passing the exam to 57.6%, not a very good trade off at all. This puzzle feels as though there is a clever scheme which will bring higher average marks with low failure rate, but this is the best I can do. Regards Mark Michell ------------------------------------------------- 1.correct 2.correct 3.false 4.correct 5.correct 6.correct 7.correct 8.correct 9.false 10.correct 11.correct Evgeni Lukin ------------------------------------------------- TTFTTFTTFTT Really neat little puzzle--with real-world applications, too! It's stuff like this that I owe a lot of my success in school to. ;-) --David Sprehn ------------------------------------------------- Dear Sir/Madam, How is: 1. Correct 2. Correct 3. False 4. Correct 5. Correct 6. False 7. Correct 8. Correct 9. False 10. Correct 11. Correct Regards, Bassam Al-Harthi ------------------------------------------------- By straight enumeration, there are 288 possible tests the teacher is allowed to give (i.e., with >=6 "true" answers and no three adjacent answers the same). Assuming each allowed test is equally likely, the probability that each question will have the answer "true" is: 0.68, 0.58, 0.47, 0.58, 0.56, 0.51, 0.56, 0.58, 0.47, 0.58, 0.68. So a pretty good strategy is just to always answer "true", giving 6.22 right on average; but answering "false" on the third and ninth questions improves this to 6.36 right on average. This is (still by straight enumeration) the optimal strategy for test sizes for 5<=N<=25 problems (answer "false" on the third and the third-from-last problems only), but the edge over always guessing "true" is narrowing. The obvious follow-up questions: is this always the best strategy? What is the edge in the limit of large N? Regards, -- Mike Quist ------------------------------------------------- By enumerating all possible sets of correct answers, and choosing the most probable correct answer to each question; the students should answer [1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1], where 1 means "correct" and 0 "false". for an average score of 916/144 out of 11, approx= 6.36 out of 11. -- Neil Harris ------------------------------------------------- I would like to be able to say that I used a subtle symmetry argument...yeah let's go with that...but I actually programmed a brute force search which arrived at: T T F T T T T T F T T for an expected 63.36% However in this case 100% is out of the question since it breaks the rules. For optimists they can use: T T F T T F T T F T T for an exppected 63.33% Making the totally unwarranted assumption that all legal tests out of the 2048 possibilities are equiprobable. Cheers, Lyman Hurd ------------------------------------------------- Best Strategy: Study Second Best Strategy: Cheat Third Best Strategy: Write "correct" for each question. Luke Pebody