Five students each answered five questions on an exam consisting of two multiple-choice questions (A, B or C) and three True-False questions. They answered the questions as follows:
Student | Q1 | Q2 | Q3 | Q4 | Q5 |
a | A | A | T | T | T |
b | B | B | T | F | T |
c | A | B | T | T | F |
d | B | C | T | T | F |
e | C | A | F | T | T |
No two students got the same number of correct answers. Who got the most correct answers?
On a second exam, ten students answered five multiple-choice questions (A, B, C, D or E) and five True-False questions. No two students got the same number of correct answers. Determine who got the most correct answers. They answered the questions as follows:
Student | Q1 | Q2 | Q3 | Q4 | Q5 | Q6 | Q7 | Q8 | Q9 | Q10 |
a | C | C | B | D | D | T | F | F | F | F |
b | A | C | D | E | A | F | T | F | F | F |
c | A | B | E | C | B | T | F | T | T | T |
d | C | D | A | E | B | T | F | F | F | F |
e | C | C | E | D | A | F | T | F | F | F |
f | C | E | A | C | E | F | F | T | T | T |
g | A | B | A | C | E | T | F | F | T | T |
h | B | B | D | C | A | T | F | F | F | F |
i | E | E | C | C | B | T | T | T | T | T |
j | A | B | C | C | D | F | F | F | T | T |
Source: Reader Jimmy Chng Gim Hong.
Student | Q1 | Q2 | Q3 | Q4 | Q5 | Score |
Answers: | B | C | T | F | F | |
a | A | A | T | T | T | 1 |
b | B | B | T | F | T | 3 |
c | A | B | T | T | F | 2 |
d | B | C | T | T | F | 4 |
e | C | A | F | T | T | 0 |
Student | Q1 | Q2 | Q3 | Q4 | Q5 | Q6 | Q7 | Q8 | Q9 | Q10 | Score |
Answers: | A | B | A | C | E | T | F | T | T | T | |
a | C | C | B | D | D | T | F | F | F | F | 2 |
b | A | C | D | E | A | F | T | F | F | F | 1 |
c | A | B | E | C | B | T | F | T | T | T | 8 |
d | C | D | A | E | B | T | F | F | F | F | 3 |
e | C | C | E | D | A | F | T | F | F | F | 0 |
f | C | E | A | C | E | F | F | T | T | T | 7 |
g | A | B | A | C | E | T | F | F | T | T | 9 |
h | B | B | D | C | A | T | F | F | F | F | 4 |
i | E | E | C | C | B | T | T | T | T | T | 5 |
j | A | B | C | C | D | F | F | F | T | T | 6 |
1. First, notice that there cannot be both a score of 0 right and a score of all right. Two such scores would have to have answered every question differently, but there is at least one true-false question answered True by any pair of students. So the scores must be 1-2-3-4-5 or 0-1-2-3-4. The maximum number of correct answers given for each question is equal to the times the most frequent answer for that question was given. The most frequent answers are A & B tied for both 1 & 2 and True for all the true-false questions, qith frequencies of 2, 2, 4, 4, and 3 for a total of 15. If the distribution is 1-2-3-4-5 then we need all these answers to be correct (for some combination of the A & B answers on the first two). Since A is the only person to answer True for all of 3-5, he must be the one who got all the questions right, so A is right for 1 & 2. But this gives scores of 5, 2, 3, 2, 3. So we must instead have scores of 0-1-2-3-4. With a total of 10 right answers, we need 1 or 2 of the T-F questions to be True. With all 3, you get too many right answers, and with none, you get not enough. With 2 True answers, everybody gets at least one correct answer, so you don't have a 0. So there must be one T-F question that is True. Since only one of them is true, nobody got all 3 T-F questions right, and so one of students b through e must have gotten both of the first two right. This leads to eight cases for the right answers (each student's answers for A & B plus one of his True answers correct and one wrong) which can easily be checked to see if they give the right scores. =====1 BBAABBCC =====2 BBBBCCAA =====3 TFTFTFFF =====4 FFFTFTTF =====5 FTFFFFFT 12345 AATTT 11221122 BBTFT 44313102 ABTTF 31442220 BCTTF 31224420 CAFTT 02020244 Only the answer set B, C, T, F, F works. Student d got the most correct answers, with 4. 2. As in the first part, we again see that no two students answered all the questions differently. Student c answered the T-F questions exactly opposite of students b and e, but shared a multiple-choice answer with each of them. So we have either 0-1-2-3-4-5-6-7-8-9 or 1-2-3-4-5-6-7-8-9-10 correct answers, for a total of 45 or 55. The maximum correct answers for the questions are 4 (A or C), 4 (B), 3 (A), 6 (C), 3 (A or B), 6 (T), 7 (F), 7 (F), 5, and 5, for a total of 50. So we have 0-1-2-3-4-5-6-7-8-9 scores, and nobody got all the questions right. There must be a student with 9 correct answers and another with 8 correct answers. These two must have at most 3 answers different. Inspection shows that these can only be b and e, or c and g, or g and j. In each case exactly 7 answers match, so these 7 must all be correct, and one or the other is correct on each other question. In the b and e case, the correct answers are C for 2, A for 5, and FTFFF for the T-F questions. This leads to partial scores (scoring only these 7 questions) of 4, 7, 0, 3, 7, 1, 1, 4, 1, 2. Only students a and h could be the one who got 7 correct answers, and only if they got their other three questions all correct. However, neither student's answers on questions 1, 3, and 4 match enough of b's and e's answers to give them 8 and 9 correct. In the g and j case, the correct answers are A for 1, B for 2, C for 4, and FFTT for the last four. This gives partial scores of 2, 2, 6, 2, 1, 4, 7, 4, 3, 7. There is no student in this set with a possible score of 0 so this is not the correct assumption. In the c and g case, the correct answers are A for 1, B for 2, C for 4, and TF?TT for the T-F questions besides 8. This gives partial scores: 2, 1, 7, 2, 0, 4, 7, 4, 4, 6. Only student e could have gotten all the answers wrong, which tells us that E is wrong for 3 (so A must be right), A is wrong for 5, and F is wrong for 8 (so T is right). The new partial scores (only omitting question 5) are: 2, 1, 8, 3, 0, 6, 8, 4, 5, 6. Either B or E must be right for question 5, and students a, b, d, and e must not have gotten this one right in order to have scores of 0 through 3. Since d answered B, E must be right, giving scores of 2, 1, 8, 3, 0, 7, 9, 4, 5, 6 which is what we want. The answers are thus ABACETFTTT and g got the most correct with 9. Joseph DeVincentis
ANSWERS In Problem 1 the best score is 4, obtained by student d, whose wrong answer concerns Q4. In Problem 2 the best score is 9, obtained by student g, whose wrong answer concerns Q8. ================================== A FIRST PIECE OF STRATEGY Each student can assign a "score" to its collegues by comparing theyr answers with its own (one point for coinciding answers, zero points for different answers). If a student gave all correct answers, the scores that it will assign are the right ones; thus, because of the assumptions: <> these points should be all different. In both problems this does not happen, thus the "true" scores are the five values 0,...,4 for problem 1, and the ten values 0,...,9 for Problem 2. On the other hand, also when no one got the maximum, the notes assigned by the best student (4 good answers in Problem 1, 9 in Problem 2) must satisfy a restriction: each assigned value can differ from the true one at most by one unit. Let us show how this works in problem 2: - Student a can not be the winner: its scores are 10, 4, 2, 6, 6, 2, 3, 5, 1, 3 where of course the 10 is the auto-evaluation. The 10 must become 9, but no value can become 8. - Student b can not be the winner; its scores are: 4, 10, 1, 4, 7, 1, 2, 5, 1, 3 and now the 8 can be reached by modifying the 7; but then there is no way of recover the value 7. - By using similar arguments we get that only student c or student g can be the winner; the corresponding notes being respectively: 2, 1, 10, 3, 1, 5, 7, 4, 6, 6 3, 2, 7, 4, 1, 6, 10, 5, 4, 7 in both cases, by modifying at most by a unit each value, we can get the whole series of values 0,1,...,9. To conclude the study of Problem 2 we can apply a second idea we will detail in the framework of Problem 1. Let us remark, however, that THIS STRATEGY COULD EASELY BE ADAPTED TO BUILD A NON-BRUTE-FORCE SOLUTION BY MEANS OF A COMPUTER PROGRAM: instead of check the answers with respect to all the 10^10 possible cases, we can confine ourselves to at most 350 cases: for each of the 10 students we explore the 35 possibilities corresponding to the fact that he did at most one error... ================================= A SECOND PIECE OF STRATEGY In the answers-table, let us replace any letter (A, B, C, T, F) by the number of students that gave such answer; thus, the last column being the sum of each row: 2,2,4,4,3-->15 2,2,4,1,3-->12 2,2,4,4,2-->14 2,1,4,4,2-->13 1,2,1,4,3-->11 We already know that the evaluations of the 5 students are, in some order, the values 0,...,4; thus theyr sum is 10. On the other hand the row corresponding to the best student contains only one error; a single modification in this row must bring the total to 10. The allowed changes are: - in column 1, only 1<-->2; - in columns 3 and 4, only 1<-->4; - in column 5 only 2<-->3. The only possibilities are concerned with students d (a 4 becomes 1) and e (the 3 becomes 2; or the 2 becomes 1). This last case (best=e) is however impossible: both changes would bring to two students with score 2.