Skip to main content

"Codes" in which a group of words are pairwise different at a certain position

I read the following problem, claimed to be in the IMO shortlist in 1988:

A test consists of four multiple choice problems, each with three options, and the students should give an unique answer to each problem. After the test, one finds that for every three students, there is one problem to which their answers are pairwise different. What is the maximum number of students who took the test?

The answer is 9, with the following construction (actually a ternary code of length $4$ and hamming distance $3$).

1:0000    2:0111    3:0222
4:1012    5:1120    6:1201
7:2210    8:2102    9:2021

The following is my question:

Let $C$ be a set of $q$-ary words of length $\ell$. What is the maximum size of $C$ such that, for any $k$ words ($k\le q$), there is a position at which the $k$ words are pairwise different?

When $k=2$, this is the usual $q$-ary code with hamming distance $1$. Corresponding to the problem above, we have $q=3$, $\ell=4$ and $k=3$.

I don't know if this problem is previously studied. I didn't find any general answer.

More specifically, can you give an answer for $q=3$, $\ell=6$ and $k=3$?

Hao Chen
  • 2.6k
  • 19
  • 29