What is the maximum collection of $n$-tuples, such that any two elements in the collection have different values in at least $3$ positions

Question

A $n$-tuple $(x_1,x_2,...,x_n)$, where $1 \leq x_1 \leq m_1$, $1 \leq x_2 \leq m_2$, and goes on until $1 \leq x_n \leq m_n$. And $m_i's$ are natural numbers and are in non-decreasing order ( $m_1 \leq m_2,...\leq m_n$ ). How can we find the collection of $n$-tuple such that any two elements in the collection have different values in at least $3$ positions. So at least $3$ positions need to have different values for any two elements in the collection, I was thinking of choosing the last $2$ position values and in remaining $n-2$ positions, any one or more positions. ( Since I have more choices for $x_{n-1}$ and $x_n$). Let me take an example.$n=4$. $$m_1=2, m_2=3,m_3=4,m_4=5 $$. I found that the below collection is maximal.(i.e You cannot add any other element to the collection) $$1111,1222,1333,2123,2231,2312$$ But is it the collection with the maximum cardinality ? Note that I have not used $4$ and $5$ in $3^{rd}$ and $4^{th}$ position. Can I get a better collection if I use them. I failed to get more than $6$ elements. By taking some more examples and writing the n-tuples in similar fashion, I am observing that cardinality of the collection is $$m_1 \times m_2 \times ... \times m_{n-2}$$ Is there a way to prove or disprove it ? How can I find the maximum possible cardinality for a given $m_i's$ ?

Answer 1

For your example with $n=4$ and $m=(2,3,4,5)$, the maximum cardinality is indeed $6$. I solved this instance as a maximum independent set problem in a graph with a node per tuple and an edge if the two tuples agree in at least $2$ positions.

Explicitly, I used an integer linear linear programming formulation, with a binary decision variable $y_i$ to indicate whether node $i$ is selected. The problem is to maximize $\sum_i y_i$ subject to $y_i + y_j \le 1$ for each edge $(i,j)$.

Answer 2

Counting Argument

Note: I presume the ordering in the n-tuple does not matter since you stated you have tried to pick the last elements to duplicate.

The total number of n-tuples formed is n-tuples with exactly three duplicates, plus n-tuples with exactly four duplicates, ..., plus n tuples with n minus one duplicates, and n tuples with n minus one duplicates.

To solve one of the smaller problems, consider counting all the ways the duplicates can occur multiplied by what the rest of the n-tuple can have. For example, for a 5 tuples with 3 duplicates there are 9 ways to put the duplicates last. The other two have 2 ways so there is 18 total ways.

Therefore, the total answer should be a sum of a multiplication.

Answer 3

What you are claiming is that you can choose the first $n-2$ positions in all possible ways, then extend each of the tuples to $n$ positions in such a way that you satisfy the three difference requirement. We can show that is not always possible. Let $n=6$ and all the $m_i=2$. There are $2^4=16$ ways to choose the first $4$ bits. In particular one of them is all $0$s and $4$ of them are $3\ 0$s and one $1$. No pair of these $5$ differ in more than $2$ positions. There are then only $4$ choices for the last two bits, so by the pigeonhole principle there will be at least two that are extended by the same last two bits and those words will differ by at most two bits. This proves that we cannot always achieve the target because if two words agree in the first four bits they will not differ in three.

Your claim is a good upper bound because if we find more $n-2$ tuples than that two of them will be the same and their extended $n$ tuples cannot differ in more than two positions.