
Problem 6. Let $X$ be a set of $n+1$ elements, $n \geq 2$. Ordered $n$-tuples $\left(a_{1}, a_{2}, \ldots, a_{n}\right)$ and $\left(b_{1}, b_{2}, \ldots, b_{n}\right)$ formed from distinct elements of $X$ are called 'disjoint' if distinct indices $i$ and $j$ exist such that $a_{i}=b_{j}$. Find the maximal number of $n$-tuples any two of which are 'disjoint'.


Solution: For $n \geq 2$ denote by $A(n+1)$ the maximum number of ordered $n$-tuples such that any two of them are 'disjoint'. Also let $S(X)$ be a set of such $n$-tuples for which $|S(X)|=A(n+1)$. It is clear that for any $\alpha \in X$ the following holds:

$$
\left|\left\{\left(a_{1}, a_{2}, \ldots, a_{n}\right) \in S(X) \mid a_{1}=\alpha\right\}\right| \leq A(n)
$$

Thus $A(n+1) \leq(n+1) A(n)$. Therefore

$$
A(n+1) \leq(n+1) n \ldots A(3)
$$

Direct verification shows that $A(3)=3$, so $A(n+1) \leq \frac{(n+1)!}{2}$.

We prove now that $A(n+1)=\frac{(n+1)!}{2}$ by constructing a set of $\frac{(n+1)!}{2}$ ordered $n$-tuples, any two of which are 'disjoint'. We may assume that $X=\{1,2, \ldots, n+1\}$. Consider a set $E$ of all even permutations of $1,2, \ldots, n+1$. (A permutation $\left(a_{1}, a_{2}, \ldots, a_{n+1}\right)$ is called even if the number of pairs $(i, j)$ such that $ia_{j}$ is an even number.) The set

$$
\left\{\left(a_{1}, a_{2}, \ldots, a_{n}\right) \mid\left(a_{1}, a_{2}, \ldots, a_{n}, a_{n+1}\right) \in E\right\}
$$

has $\frac{(n+1)!}{2}$ ordered $n$-tuples, any two of which are 'disjoint'.

