Let \(Q\) be a set of permutations of \(1,2,...,100\) such that for all \(1\leq a,b \leq 100\), \(a\) can be found to the left of \(b\) and adjacent to \(b\) in at most one permutation in \(Q\). Find the largest possible number of elements in \(Q\).
Problem
Source: China Northern Mathematical Olympiad 2017
Tags: graph theory, combinatorics
29.07.2017 16:10
Please clarify "to the left of $b$". Does it necessary that $a$ must be adjacent to $b$?
29.07.2017 16:12
Sorry, yes, it is necessary.
29.07.2017 16:41
The answer is 100. Consider the general case $1,2,\ldots,2n$. If $\left|Q\right|>2n$, there are more than $\frac{(2n)!}{(2n-2)!}$ possible ways of selecting ordered number pair $(a,b)$. According to Pigeonhole Principle, at least one pair $(a_0,b_0)$ is repeated, a contradiction. When $\left|Q\right|=2n$, here is the construction (written in permutation and in modular meaning): Permutation $k(1\leq k\leq 2n)$ is \[\{k, k+1, k-1, k+2, k-2, \ldots, k+n-1, k-(n-1), k+n\}\bmod 2n\]Notice that the absolute value of difference in the neighbouring term is $1, 2, 3, \ldots, n-1, n, n-1, \ldots, 2, 1$, and we are done. Let $2n=100$ and we get what we want.
29.07.2017 18:02
Uhh, how do we cover a complete graph \(K_{2n}\) using \(n\) paths and with each path of length \(2n-1\)?
29.07.2017 19:15
I have a consruction for $p-1$, where $p$ is a prime number. For each $1\leq i\leq p-1$, let the $i$th permutation be $\{ik\pmod p\}_{k=1}^{p-1}$