4
$\begingroup$

I'm making a weighted test, i.e. a test with N yes/no questions where the score differs from question to question. For simplicity assume that the sum of all individual scores is 100 and assume the test is passed if the achieved score is 70 or more.

Now I like to make sure that all questions are relevant for passing/failing the test.

Simple example of good test:

Q1 gives 30
Q2 gives 30
Q3 gives 40

The test can be passed by the following correct answers: Q1+Q3, Q2+Q3 (and Q1+Q2+Q3) So all questions can be relevant for passing or failing.

Simple example of bad test:

Q1 gives 10
Q2 gives 45
Q3 gives 45

In this case it doesn't matter whether the answer to Q1 is right or wrong as it can't change the pass/fail result of the whole test.

So my question is:

In a N question test with a given list of scores per question how do I check that all questions can impact the pass/fail result of the whole test?

If I look at a specific answer with score S, I need to prove that some combination of right/wrong answers to the other questions can give a total score in the range [70-S:69]. But I'm not sure how to do that.

$\endgroup$
  • $\begingroup$ This smells of knapsacking to me... $\endgroup$ – Tiwa Aina Nov 30 '17 at 21:23
3
+50
$\begingroup$

Your simple question turned out to be very deep, because in fact you are asking how to test whether a given weighted voting system has a dummy. This should be a well-known question, so I googed for it. Surprisingly, I found no references. A bit later I understood why I failed. Clearly, a weighted voting system (test) has a dummy iff a question with a smallest weight $S$ is a dummy. As you have observed, this holds iff there exists no combination of right/wrong answers to the other questions with a total score in the range $[70-S:69]$. But this is, in fact, the subset sum problem, which is known to be NP-hard. In particular, there should be no known algorithm which solves it in a polynomial time. In Wikipedia’s article is noted that if the number of questions is small, then an exhaustive search for the solution is practical.

$\endgroup$
  • $\begingroup$ Thanks for your feedback. I have one question for your answer - you write: "Clearly, a weighted voting system (test) has a dummy iff a question with a smallest weight S is a dummy." Can you put a few extra word to explain why I only need to look at the smallest ? It may be obvious but right now I fail to understand why. $\endgroup$ – 4386427 Dec 4 '17 at 6:11
  • $\begingroup$ @4386427 This follows from the following characterization. Assume that we have a set $\mathcal Q_0=\{Q_1,\dots, Q_N\}$ of questions with weights (scores) $S_1,\dots, S_N$ respectively. A question $Q_i$ with weight $S_i$ is a dummy iff for each set $\mathcal Q\subset \mathcal Q_0$ of questions with $\sum_{Q_j\in\mathcal Q} S_j< 70%$ we have $\sum_{Q_j\in\mathcal Q\cup\{Q_i\}} S_j< 70%$. $\endgroup$ – Alex Ravsky Dec 4 '17 at 6:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.