Let $X$ be a set with $n$ elements and $0 \le k \le n$. Let $a_{n,k}$ be the maximum number of permutations of the set $X$ such that every two of them have at least $k$ common components (where a common component of $f$ and g is an $x \in X$ such that $f(x) = g(x)$). Let $b_{n,k}$ be the maximum number of permutations of the set $X$ such that every two of them have at most $k$ common components. (a) Show that $a_{n,k} \cdot b_{n,k-1} \le n!$. (b) Let $p$ be prime, and find the exact value of $a_{p,2}$.
Problem
Source: MOP 2005 Homework - Black Group #8
Tags: modular arithmetic, combinatorics unsolved, combinatorics
math_explorer
29.05.2014 06:05
Let $S$ be the set of permutations of $X$. (a) The obvious combinatorial interpretation of proving the desired statement is finding an injection from $A \times B$ to $S$ for any sets $A, B \subset S$ where every two permutations in $A$ have at least $k$ common components and every two permutations in $B$ have at most $k-1$ common components. This is surprisingly easy; just compose the two permutations, applying the permutation from $A$ first. This is why it's an injection. If $a_1, a_2 \in A$ and $b_1, b_2 \in B$ then there exist $k$ elements $x$ such that $a_1(x) = a_2(x)$. By the definition of $B$, for the at least $k$ elements $x'$ that are in the image of a common component of $a_1$ and $a_2$, we can't have $b_1(x') = b_2(x')$ for all such elements. Then consider what component $x$ of $a_1, a_2$ mapped to $x'$, and note that $b_1 \circ a_1(x) \neq b_2 \circ a_2(x)$ so $b_1 \circ a_1 \neq b_2 \circ a_2$ (b) $a_{p,2} = (p-2)!$. The construction is obvious; just fix values on two elements and take all $(p-2)!$ permutations of the rest. The bounding is also easy with (a): note that $b_{p,1} \geq n(n-1)$ by taking all invertible linear maps mod $p$, that is $f : \mathbb{Z}/p\mathbb{Z} \to \mathbb{Z}/p\mathbb{Z}$, $f(x) = rx + s$ for $r \in \{1, 2, \ldots, p-1\}$ and $s \in \mathbb{Z}/p\mathbb{Z}$.
AnonymousBunny
02.09.2014 14:16
Let $f_k (n)$ denote a set of permutations of $\{1, 2, \cdots , n\}$ any two of which share at least $k$ elements, and let $g_k (N)$ denote a set of permutations of $\{1, 2, \cdots , n\}$ no two of which share more than $k-1$ elements.
Claim: For any permutations $p_1, p_2 \in f_k (N)$ and $p_3, p_4 \in g_k (N),$ $p_1 \odot p_3 \neq p_2 \odot p_4$ (where $\sigma \odot \varphi$ denotes composition of permutations $\sigma$ and $\varphi$).
Proof: Note that permutations $p_1, p_2$ have more common components than permutations $p_3, p_4,$ so there exists an $x$ such that $p_1 (x) = p_2 (x)$ but $p_3 (x) \neq p_4 (x).$ Then, we have $p_1 \odot p_3 (x) \neq p_2 \odot p_4 (x).$ $\blacksquare$
Hence, any two permutations from $f_k (N)$ and $g_k (N)$ correspond to a unique permutation of $\{1, 2, \cdots , n\}.$ It follows that $|f_k (N) \times g_k (N) | = |f_k (N)| |g_k (N)|$ is at most the total number of permutations of $\{1, 2, \cdots , n\}$, i.e. $a_{n, k} \cdot b_{n, k-1} \leq n!.$ $\blacksquare$
Claim: $b_{p, 1} \geq p(p-1)$
Proof: For all $1 \leq a \leq p-1, 1 \leq b \leq p,$ let $\sigma_{a, b} = \{ai+b \pmod{p}\}_{i=1}^{p}.$ First, I shall show that $\sigma_{a, b}$ forms a permutation of $\{1, 2, \cdots , p\}$ for all $a \in [1, p-1], b \in [1, p].$ Suppose, on the contrary, that there exist $i, j$ such that $ai + b \equiv aj + b \pmod{p}.$ This implies $p \mid a (i-j).$ Since $\gcd (a, p)=1,$ $p \mid i-j.$ However, $|i-j|$ is never more than $p-1,$ so $i-j = 0 \implies i=j.$ Now, I shall show that for any $a, b, c, d$ in that range, unless $a=c$ and $b=d,$ $\sigma_{a, b}$ and $\sigma_{c, d}$ have at most 1 common component. Let $x$ be a common component of those two permutations. First, if $a=c,$ $ax+b \equiv cx+d \pmod{p} \implies b \equiv d \pmod{p} \implies b=d,$ which is impossible, so there are no common components. Now suppose $a \neq c, b \neq d.$ We have $ax+b \equiv cx+d \pmod{p} \implies x \equiv (d-b) I \pmod{p},$ where $I$ denotes the multiplicative inverse of $c-a \pmod{p}.$ Hence, $x$ has only one possibility modulo $p,$ which uniquely determines $x.$ It follows that the set of permutations $\{\sigma_{a,b}\}_{\substack{ 1 \leq a \leq p-1 \\ 1 \leq b \leq p}}$ has the property that any two elements in it share at most 1 common component. This set obviously has $p(p-1)$ elements, so we're done. $\blacksquare$
Now, from the first part, it follows that $a_{p, 2} \leq \dfrac{p!}{p(p-1)} = (p-2)!$. Considering the set of permutations $\varphi$ that satisfy $\varphi(1) = 1, \varphi(2) = 2,$ we see that equality must hold (once two elements are fixed, there are $(p-2)!$ possibilities for $\varphi$ and any two of them share the common components 1 and 2). Hence, the answer is $(p-2)!.$
Note that as a consequence, we must also have $b_{p, 2} = p(p-1).$