At a mathematical competition $n$ students work on $6$ problems each one with three possible answers. After the competition, the Jury found that for every two students the number of the problems, for which these students have the same answers, is $0$ or $2$. Find the maximum possible value of $n$.
Problem
Source:
Tags: combinatorics
toshihiro shimizu
19.07.2017 20:52
Answer: $n=18$ Let the choice of these problem be 0, 1, 2. We first show that $n>18$ is impossible. We can find 7 student who answered same answer in problem 1. WLOG, let the answer be 0. Then, we can also find 3 students among these 7 students who answered same answer in problem 2. WLOG, let the answer be 0. Then, these 3 students answered each of other problem differently. WLOG, we can assume these 3 students answer as follows; A: 0, 0, 0, 0, 0, 0 B: 0, 0, 1, 1, 1, 1 C: 0, 0, 2, 2, 2, 2 We take another student $S$ who answered 0 in problem 1. $S$ has 2 problems among problem 3, 4, 5, 6 which answered same. If this answer is 0, A and S has three problems which answered same. Other case is similar. For $n=18$ we have an example; 2 0 2 2 2 0 2 2 0 0 2 1 0 1 2 2 1 2 1 1 2 1 2 1 2 1 1 2 0 1 2 1 0 1 1 0 1 2 1 2 2 2 0 2 0 2 0 0 0 0 0 1 2 2 1 1 0 0 0 2 0 0 2 0 0 1 0 1 1 0 2 0 1 0 0 2 1 1 2 0 1 0 1 2 0 2 1 1 1 1 1 2 2 0 1 0 1 0 1 1 0 0 2 2 2 1 0 2 (I used sugar solver to find this example. Is there any mathematical example?)
McTeague
18.08.2018 17:21
For $x \in \{1,2,3,4,5,6\}$, call two $6$-tuples $x$-similar if they match in exactly $x$ entries. (A set of $6$-tuples then satisfies the problem statement if and only if each pair of them is either $0$-similar or $2$-similar.)
Start with the following six $6$-tuples:
\begin{align*}
(0,0,0,0,0,0)\\
(1,1,1,1,1,1)\\
(2,2,2,2,2,2)\\
(0,0,1,1,2,2)\\
(1,1,2,2,0,0)\\
(2,2,0,0,1,1)
\end{align*}It is clear that the first three $6$-tuples are each pairwise $0$-similar as are the last three. Since each of the last three have two each of $0$, $1$, and $2$, any of the first three is $2$-similar to any of the last three.
For the other $12$ $6$-tuples, consider $Y = (0,1,2,0,2,1)$ and two types of operations permuting the entries of a $6$-tuple. Define an $A$ operation to be a cyclic shift two to the right. (So $A(0,1,2,0,2,1) = (2,1,0,1,2,0)$.) For $i \neq j$, define $B_{i,j}$ to be the permutation which swaps entry $2i-1$ with entry $2i$ and entry $2j-1$ with $2j$. (So $B_{1,2}(0,1,2,0,2,1) = (1,0,0,2,2,1)$.)
In cycle notation, we are taking all permutations $a^ib^j$ where $a = (1\text{ }2)(3\text{ }4)$ and $b = (1\text{ }3\text{ }5)(2\text{ }4\text{ }6)$ with $i = 0, 1$ and $b = 0, 1, 2$ and applying these to $Y$. Since $(3\text{ }4)(5\text{ }6)(1 \text{ } 3 \text{ } 5)(2 \text{ } 4 \text{ } 6) = (1 \text{ } 3 \text{ } 5)(2 \text{ } 4 \text{ } 6)(1 \text{ }2)(3 \text{ }4)$, it suffices to check that each of the other $17$ permutations matches $(2,1,0,1,2,0)$ in $0$ or $2$ positions, which can be easily checked to be true.
The full list\begin{align*}
(0,0,0,0,0,0)\\
(1,1,1,1,1,1)\\
(2,2,2,2,2,2)\\
(0,0,1,1,2,2)\\
(1,1,2,2,0,0)\\
(2,2,0,0,1,1)\\
(0,2,1,2,0,1)\\
(0,2,2,1,1,0)\\
(0,1,2,0,2,1)\\
(0,1,0,2,1,2)\\
(2,0,1,2,1,0)\\
(2,0,2,1,0,1)\\
(1,0,0,2,2,1)\\
(1,0,2,0,1,2)\\
(1,2,1,0,2,0)\\
(2,1,1,0,0,2)\\
(2,1,0,1,2,0)\\
(1,2,0,1,0,2)\\
\end{align*}
Assume for contradiction that we had $n \ge 19$ $6$-tuples satisfying the problem's conditions. There are $3 \cdot 3 = 9$ possible pairs for the first two entries of any $6$-tuple so by the pigeonhole principle, some pair occurs at least $\left\lceil \frac{19}{9} \right\rceil = 3$ times as the first two entries. WLOG it is $(0,0)$. Take three such $6$-tuples $a$,$b$,$c$ which begin with $(0,0)$. $a$,$b$,$c$ are then pairwise $2$-similar from their first two positions and so are pairwise different in their other four positions. In particular, one of $a,b,c$ has $0$ in entry $3$, $1$ in entry $3$, and $2$ in entry $3$, and likewise for entries $4$,$5$, $6$.
Thus, from the pigeonhole principle, any fourth $6$-tuple has to be $2$-similar to two of $a,b,c$ with the matched entries being from among positions $3,4,5,6$. In other words, any fourth $6$-tuple is $0$-similar to one of $a,b,c$.
Now count the cardinality of the set $Z$ of pairs $((r,s),i)$ where $r$ and $s$ are distinct $6$-tuples from among those in the collection such that $r$ and $s$ match at index $i$.
Counting by pairs $(r,s)$, there are at most $2\binom{n}{2}$ such pairs. However, as just mentioned above, any of the $6$-tuples other than $a,b,c$ are $0$-similar to one of these three $6$-tuples. Thus, $|Z| \le 2\binom{n}{2} - 2(n-3) = n^2-3n+6$.
Counting by indices, let $A_i$ be the number of $6$-tuples with a $0$ at index $i$ and defined $B_i$ for $1$s and $C_i$ for $2$s similarly. Then $|Z| = \sum_{i=1}^{6} \binom{A_i}{2} + \binom{B_i}{2} + \binom{C_i}{2}$. Since all the $6$-tuples in the collection other than $a,b,c$ have non-zero entries in positions $1$ and $2$, $a_1 = a_2 = 3$ and $b_1 + c_1 = b_2 + c_2 = n-3$. Using the convexity of $f(x) = \frac{x^2-x}{2}$ and Jensen's inequality:
\begin{align*}
|Z| &= \sum_{i=1}^{6} \left(\binom{A_i}{2} + \binom{B_i}{2} + \binom{C_i}{2}\right) \\
&= \sum_{i=1}^{2} \left(3 + \binom{B_i}{2} + \binom{C_i}{2}\right) + \sum_{i=3}^{6} \left(\binom{A_i}{2} + \binom{B_i}{2} + \binom{C_i}{2}\right) \\
&\ge 6 + 4 \binom{\frac{n-3}{2}}{2} + 12 \binom{\frac{n}{3}}{2} \\
&= \frac{7}{6}n^2 - 6n + \frac{27}{2} \\
\Longrightarrow n^2-3n+6 &\ge \frac{7}{6}n^2 - 6n + \frac{27}{2} \Longleftrightarrow 0 \ge (n-3)(n-15) \Longleftrightarrow 3 \le n \le 15
\end{align*}This is a contradiction and $n \le 18$.
The witness for $18$ that I gave was not something that I "just thought of". I found the bound of $n \le 18$ from above first. The proof above also shows that for $n = 18$, any index pair cannot have the same pair of values more than twice. In particular, any $6$-tuple can only then be $2$-similar to $\binom{6}{2} = 15$ other $6$-tuples in the collection, leaving $2$ that it is $0$-similar to. Running the same sort of argument as above again, for $n = 18$ to be feasible, any witness has to be such that each $6$-tuple in the collection is $2$-similar to $15$ of the other $6$-tuples in the collection and $0$-similar to the other two. Furthermore, each of $0$, $1$, and $2$ must occur $6$ times at any index among the elements of the collection of $18$.
With that information as a guide, I began with $(0,0,0,0,0,0), (1,1,1,1,1,1), (2,2,2,2,2,2),$ and $(0,0,1,1,2,2)$ and started producing $6$-tuples that matched the fourth of these in a distinct pair of two positions and which had two each of $0$,$1$,$2$.
I think that formal construction for the witness that I gave can also be described by considering a cube and labeling the front face with $0$, the back face with $1$, the right face with $2$, the left face with $0$, the bottom face with $1$, and the top face with $2$, then considering the actions of rotating by multiples of $120^{\circ}$ around a vertex and by multiples of $90^{\circ}$ around a face to get $12$ different labelings.