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

Question

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.

Answer 1

This is a partial answer: the maximum possible number of students is at least 6, and no more than 9.

Lower bound: maximum is at least 6

For this part, we want to show that it's possible to have 6 students' tests that satisfy the given criteria, namely, any two students' tests differ in at least 3 questions. The following set of tests work, where $0$ denotes false and $1$ denotes true:

000000
111111
111000
001110
010101
100011

Upper bound: maximum is no more than 9

For this part, we want to show that it's impossible to have 10 or more students; therefore, the maximum cannot be 10 or larger, and must be at most 9.

To do this, we count as follows: For a given student's test (one of $2^6 = 64$ possible tests), there are $7$ tests that differ in $0$ or $1$ answers from that test: namely, the same test, and one test which differs in each of the six questions. Imagine making a "cluster" around the student's test, consisting of these $7$ tests.

I claim that for any two students, the clusters around the two students' tests do not intersect. Suppose they did intersect: the cluster for test $A$ intersects with the cluster for test $B$. Then that means there's some test $X$ (not a real student's test, a hypothetical test) that's in both clusters. Note that:

• $X$ is in $A$'s cluster, so $X$ differs from test $A$ in at most one answer.

• $X$ is in $B$'s cluster, so $X$ differs from test $B$ in at most one answer.

• Therefore, $A$ differs from $B$ in at most $2$ answers (namely, the 1 answer that $A$ has differing from $X$, and the 1 answer that $X$ has differing from $B$). But this contradicts the fact that any two students' tests must differ in at least 3 answers.

In summary, we have formed a cluster of $7$ tests around each student's test, such that those clusters must not intersect. If there are $n$ students, then there are $7n$ total tests in all clusters and $64$ total possible tests, so $$ 7n < 64 $$ that is, $n \le 9$.

Answer 2

To see that $9$ is impossible:

Note that if you only had $4$ questions you could have no more than $2$ students whose pairwise answers differed by at least three questions. Indeed, pick one of the students. Relabeling if necessary we can assume that this student chose $TTTT$. Any other student would need to have chosen at least three $F's$, but then no any third student who chose at least three $F's$ would have to match the second in at least two places.

Now, take your proposed group of $9$ students. Since there are exactly $4$ ways to respond to the first two questions, there must be at least $3$ students who match on the first two. By the preceding comment, however, this is not possible.

Answer 3

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