How to maximize the differences between multiple versions of a quiz

50 Views Asked by At

To help detect cheating, I can create multiple versions of a quiz, with 1 or 2 changed questions on each version.

If I create alternate versions of 3 of the questions, I can create 4 versions of the quiz and ensure that any two different versions have exactly 2 questions different between them, by arranging the question like this:

         | Question 1 | Question 2 | Question 3 |
| Quiz 1 |   ver 1    |   ver 1    |   ver 1    |
| Quiz 2 |   ver 2    |   ver 2    |   ver 1    |
| Quiz 3 |   ver 2    |   ver 1    |   ver 2    |
| Quiz 4 |   ver 1    |   ver 2    |   ver 2    |

Any 2 quizzes from the table above have exactly two questions different between them.

This could also be expressed as 4 binary numbers that have 2 bits different between any pair: 000, 110, 011, and 101.

What is the mathematical principle here, and how could this be expanded to a larger number of questions and quizzes?

1

There are 1 best solutions below

2
On BEST ANSWER

The difference between two versions is the Hamming distance between the binary numbers representing the two. It just counts the number of bit positions that disagree. The Hamming codes give you the number of questions that you need to have two versions of to get a distance of three. The Hamming $(7,4)$ code says you can get $2^4$ different tests at a minimum distance of $3$ with $7$ questions that have two versions.