Maximum number of students such that they all have at least 3 out of 6 different answers.

coding-theorycombinatoricsgraph theory

A teacher made a test for his mathematics class with 6 true or false questions. When he received the tests, he noticed that any pair of students had at least three diferent answers. Since all the students answered every question, what's the maximum number of students of the class?

Here is my take. $2^6=64$ diferent tests. For one of those tests, there are $^6C_3+^6C_4+^6C_5+^6C_6$=42 tests which have 3 or more diferent questions from it.
$42/63 = 2/3$, and if the ratio stands for successive pairs of tests, ${3/2}^{10}<63<{3/2}^{11}$ then 10 students. This argument is clearly fallacious and unfounded, but I found no better.

Best Answer

You can model this as a maximum clique problem in a graph (equivalently, maximum independent set in the complement) with 64 nodes $\{0,\dots,2^6-1\}$ and an edge if the Hamming distance is at least 3. The maximum is 8:

 0 000000 
 7 000111 
25 011001 
30 011110 
42 101010 
45 101101 
51 110011 
52 110100
Related Question