Determine the largest integer $N$ for which there exists a table $T$ of integers with $N$ rows and $100$ columns that has the following properties: $\text{(i)}$ Every row contains the numbers $1$, $2$, $\ldots$, $100$ in some order. $\text{(ii)}$ For any two distinct rows $r$ and $s$, there is a column $c$ such that $|T(r,c) - T(s, c)|\geq 2$. (Here $T(r,c)$ is the entry in row $r$ and column $c$.)
Problem
Source: 2021 ISL C8
Tags: combinatorics
CANBANKAN
12.07.2022 15:39
Let $k$ be a fixed integer. Determine the largest integer $N$ such that there exists permutations $\pi_1, \pi_2,\cdots,\pi_N$ of $\{1,\cdots,2k\}$ such that for all $r\ne s$ there exists $1\le c\le 2k$ such that $|\pi_r(c)-\pi_s(c)|\ge 2$ The answer is $\frac{(2k)!}{2^k}$. We first bound. Let $f_r(c)=\lceil \frac{\pi_r(c)}{2}\rceil$. Observe $(f_r(1),f_r(2),\cdots,f_r(2k)) \ne (f_s(1),f_s(2),\cdots,f_s(2k))$. Note the multiset $(f_i(1),\cdots,f_i(2k))$ contains two of $j$ for each $1\le j\le k$. Since there are at most $\frac{(2k)!}{2^k}$ such $(2k)$-tuples, $N\le \frac{(2k)!}{2^k}$. Construction: We first consider when two $(2k)$-tuples $(f_r(1),\cdots,f_r(2k)), (f_s(1),\cdots,f_s(2k))$ could possibly result in their original permutations having $|\pi_r(c)-\pi_s(c)| \le 1$ for all $1\le c\le 2k$. This could only happen if I repeatedly do the following: start with $(f(1),f(2),\cdots,f(2k))$, call $1,\cdots,2k-1$ unmarked. I swap $f(i)$ and $f(j)$ only if $|f(i)-f(j)|=1$ and $\min\{f(i),f(j)\}$ is unmarked, and mark $\min\{f(i),f(j)\}$. To see why this is true, suppose it is possible for $(f(1),\cdots,f(2k)), (g(1),\cdots,g(2k))$ to clash. Then $|f(i)-g(i)|\le 1$ for all $1\le i\le 2k$. Let $f_j=\{a_j,b_j\}$ denote the two unique numbers such that $f(a_j)=f(b_j)=j$ and define $g_j$ similarly. Consider the smallest $j$ such that $f_j\ne g_j$. Then say $f(a_j)=j, g(a_j)=j+1, g(b_j)=j, f(b_j)=j+1$ (since $g(x)=j-1 \iff f(x)=j-1$ by the minimality of $j$) There is another value such that $f(c)=j$. If $g(c)\ne j$, then either $\pi_f(c) - \pi_g(c) \le -2$ or $\pi_f(a_j)-\pi_f(b_j)\le -2$. Hence $g(c)=j$ and we mark $j$. Now we construct a bijection between $b\colon (f(1),\cdots,f(2k)) \to (\pi(1),\cdots,\pi(2k))$ such that $\lceil \frac{\pi(j)}{2} \rceil = f(j)$ for all $1\le j\le 2k$. We consider the following process: Make $$b((1,1,2,2,\cdots,k-1,k-1,k,k))=(1,2,3,\cdots,2k-2,2k-1,2k)$$ Consider a queue. Initially, it has $(1,1,2,2,\cdots,k,k)$. Suppose $b((x_1,\cdots,x_{2k}))=(\pi(1),\cdots,\pi(2k)))$. Suppose I swap $x_m=j, x_n=j+1$. Suppose $x_l=j+1$ where $l\ne n$ and the bijection for this $(2k)$-tuple has not been established yet. Then I apply a three cycle shift to $(\pi(m),\pi(n),\pi(l))$ (i.e. $\pi(m)$ becomes what $\pi(n)$ was previously, $\pi(n)$ becomes what $\pi(l)$ was previously, and $\pi(l)$ becomes what $\pi(m)$ was previously). At this point, I mark $j$ and the cycle contains $\{2j,2j+1,2j+2\}$ This way, in the process of swapping to get from $(x_1,\cdots,x_{2k})$ to $(y_1,\cdots,y_{2k})$ such that it is possible to construct permutations such that their corresponding permutations to differ by at most 1 in every place, to get from their corresponding permutations $\pi_x$ to $\pi_y$, I have a composition of 3-cycles. I claim I need to go through some (possibly one) cycles, each of length $\ge 3$. Note the 3-cycles $C_1, C_2, \cdots, C_k$ pairwise differ by at least two points. This is true because each 3-cycle is formed by marking a number $j\in \{1,\cdots,2k-1\}$ and the cycle must have $\{2j,2j+1,2j+2\}$. It follows if I do more than one 3-cycle swap, the smallest marked number is $j$ then $2j,2j+1$ are in different places because they have been swapped once. Furthermore, $2j$ ends up where $2j+2$ originally is and $2j+1$ ends up where $2j$ originally is, so there exists a cycle of length $\ge 3$. It follows there exists $c$ such that $|\pi_x(c)-\pi_y(c)|\ge 2$, as desired.
dgrozev
12.07.2022 15:49
I commented on this problem in my blog, and also on some similarity to a Bulgarian NMO 2007, p2.
Anzoteh
16.07.2022 06:29
Three-cycle for the win!
In general, we can view the rows as a permutation of $1, \cdots, 2n$ (here $n=50$),
and therefore we need to find the maximal number of such permutation set $S$ such that for any pairs $\sigma_1\neq \sigma_2\in S$ we have $|\sigma_1(k)-\sigma_2(k)|$ for some $k$.
Denote such number as $f(n)$, and we claim $f(n)=\frac{(2n!)}{2^n}$.
Upper bound.
Group the set $S_{2n}$ of all permutations of $\{1, \cdots, 2n\}$ into equivalence classes determined by following: we say $\sigma_1\sim \sigma_2$ if and only if for all $i=1, \cdots, n$, $\{2i-1, 2i\}$ are in the same two positions for $\sigma_1, \sigma_2$, though could be swaped.
(For example, when $n=2$, the permutations $(1234), (1243), (2134), (2143)$ are all the permutations in the same equivalence class).
In other words, each class is characterized by partitioning $\{1, \cdots, 2n\}$ into $n$ pairs
$\{a_1, b_1\}, \cdots, \{a_n, b_n\}$ such that for a permutation $\sigma$ in this class,
$\{\sigma(a_i), \sigma(b_i)\}=\{2i-1, 2i\}$ for all $i=1, \cdots, n$.
Then, for any two permutations $\sigma_1, \sigma_2$ in this class, for each $k$ there's an $i$ such that $\{\sigma_1(k), \sigma_2(k)\}\subseteq \{2i-1, 2i\}$,
hence having $|\sigma_1(k) -\sigma_2(k)|\le 1$.
It then follows that for each class we can only choose at most one such permutation, giving the upper bound
$\frac{(2n)!}{2^{n}}$ since there are $2^n$ elements in each class
(given such partitions $\{a_1, b_1\}, \cdots, \{a_n, b_n\}$ there are two ways to place $\{2i-1, 2i\}$ for each $i$).
Construction.
We use induction on $n$, where base case $n=1$ we just need $(12)$.
Inductive step: suppose for some $n\ge 2$ we have $f(n-1)=\frac{(2n-2)!}{2^{n-1}}$ such permutations of $\{1, \cdots, 2n-2\}$. Consider, now, such collection $U_{n-1}$ of permutations.
The key idea is as follows:
[(i)]Notice that $(123), (231), (312)$ (the even permutations of $S_3$) itself would satisfy our condition, and so will the similar idea applied to their counterparts in $\{2n-2, 2n-1, 2n\}$ (we'll see why it's important later).
[(ii)] Group each permutation into $T_{x, y}$ where $x<y$ denote the positions of $\{2n-1, 2n\}$ (again, can be swapped within).
Concretely, our construction for the set $U_n$ is as follows: for each $1\le x < y\le 2n$, we consider each $\sigma\in U_{n-1}$, insert a blank space at position $x$, and then a blank space at position $y$. E.g. if $n=3, x=2, y=5, \sigma=(2341)$ then we have $(2?34?1)$ with $?$ being the blank space.
Then we insert $2n-1, 2n$ in the blank space according to the position of $2n-2$: we make $2n-1$ to come before $2n$ if and only if $2n-2$ is between the two blank spaces.
Hence the relative order of the three numbers are one of the following: $(2n-2, 2n-1, 2n), (2n-1, 2n, 2n-2)$, or $(2n, 2n-2, 2n-1)$ (or if you like, these three are cyclic shifts of each other).
This would give $|U_n|$ is $\frac{(2n-2)!}{2^{n-1}}\cdot \binom{2n}{2} = \frac{(2n)!}{2^n}$,
the optimal number.
Finally to verify, consider any $\sigma_1, \sigma_2$ in $U_n$. Consider the following cases depending on their class $T_{x, y}$ as denoted before.
Case 1. For some $x < y$ we have $\sigma_1, \sigma_2\in T_{x, y}$.
Then by induction hypothesis on the first $2n-2$ numbers these two permutations are valid by judging only on the positions of $\{1, \cdots, 2n-2\}$ (since they both come from $U_{n-1}$, and shifted at the same two positions for $\{2n-1, 2n\}$).
Case 2. For some four pairwise distinct $x_1<y_1, x_2<y_2$ we have $\sigma_1\in T_{x_1, y_1}$ and $T_{x_2, y_2}$.
Here, we have either $\sigma_1(x_1)=2n$ or $\sigma_1(y_1)=2n$, but $\sigma_2(x_1)$ and $\sigma_2(y_1)$ both $\le 2n-2$.
Case 3. Same $x_1 < y_1, x_2 < y_2$ but with exactly one overlap, say $z$ where $z\in \{x_1, y_1\}$ and $z\in \{x_2, y_2\}$.
If $\sigma_1(z)=2n-1$ then $\sigma_1(w)=2n$ where $w$ is such that $\{w, z\}=\{x_1, y_1\}$.
But then by our assumption (of one overlap), $\sigma_2(w)\le 2n-2$.
A similar verification can be done in case $\sigma_2(z)=2n$.
Hence $\sigma_1(z)=\sigma_2(z)=2n$, which leaves some $w_1\neq w_2$ such that $\sigma_1(w_1)=\sigma_2(w_2)=2n-1$. For a condition violation to happen,
we'll need $\sigma_1(w_2)=\sigma_2(w_1)=2n-2$ (they cannot be $2n$ since the spot is taken at position $z$ for both).
Such a construction, however, means $\sigma_1$ and $\sigma_2$ restricted to positions $w_1, w_2, z$ (and elements $\{2n-2, 2n-1, 2n\}$) are obtained by swapping a pair of elements from each other,
hence having different permutation parity.
This is a contradiction of the cyclic shift construction we discussed earlier.
JAnatolGT_00
26.11.2022 01:18
For $100=2M=K$ columns we claim the answer $N=\frac{(2M)!}{2^M}$. Replace rows by permutations $\pi_1,... \pi_N$ of $1,2,... ,K$. Upper bound. Say $\pi_i \sim \pi_j$ if given permutations differ by transpositions in some of pairs $(2k-1,2k).$ Then there is at most one of $2^M$ permutations from fixed class of equivalency among $\pi_i,$ which gives the desired bound $\Box$ Construction. Since in each permutation of equivalency class position of pair $2i-1,2i$ is fixed, we can take a permutation $\pi_a$, which for every integer $k>1$ induces as a cyclic shift a subpermutation of $2k-2,2k-1,2k$ and $\pi_a (1)<\pi_a(2).$ We will indirectly prove, that this indeed works, so take $r,s$ such that $\forall c\text{ } |\pi_r (c)-\pi_s (c)|\leq 1.$ Lemma. There exist a set of disjoint pairs $(i,i+1)$ from $\left \{ 1,2,...,K\right \}$ such that $\pi_r ,\pi_s$ differ by transpositions in all pairs. Proof. Notice that either $\pi_r (K)=\pi_s (K)$, or $\pi_r (K)=\pi_s (K-1)$ and $\pi_r (K-1)=\pi_s (K)$. Then removing consequentially one or two numbers we reduce the problem to trivial case $K\in \left \{ 0,1 \right \}$. Now take set $S\subset \left \{ 1,2,...,99\right \}$ of minimal numbers in above pairs. Since $\pi_r, \pi_s$ induces subpermutations of $2k-2,2k-1,2k$ with the same parity $(\diamond )$, it can be noticed that $\min S$ can only be even $2t,$ and by $(\diamond )$ we obtain $2t+2\in S.$ By induction $98\in S,$ so $\pi_r, \pi_s$ induces subpermutations of $98,99,100$ with opposite parities, contradiction $\Box$
gvole
31.05.2024 22:13
Essentially the same solution as others, but since nobody wanted to talk about their motivation I'll give mine. If you make a graph where each permutation is a vertex and two permutations are connected if they violate the given condition (ie. they are really close), then you want to find the independence number $\alpha$ of that graph. Clearly, the graph is vertex-transitive so if you want to determine any local properties you might as well just look at the neighbors of the identity permutation. If you try to determine the neighbors of the identity permutation you'll see that they are generated by "flipping" some disjoint adjacent pairs. This for example gives that the graph is $F_{k+1}$ regular where $k$ is the length of the strings we are considering and $F$ are the Fibonacci numbers. You can now find some rough estimates for $\alpha$ using Caro-Wei and counting arguments which gives you a little intuition on the order of magnitude of the answer. (If it wasn't obvious enough already...) Now finding any meaningful upper or lower bound becomes untractable in the general case so you might try small cases. The first time something meaningful comes up is with $k=4$. Here every vertex belongs to a $K_4$, so we know that $\alpha \le 6$ and constructing it is very easy now. We see that this is because all the strings obtained by pairing up adjacent bits and flipping some of them are necessarily connected. This gives the bound of $\frac{k!}{2^{\frac k2}}$ for even $k$ which seems to be optimal. Constructing this is the difficult part of the problem. Any explicit construction you try just. doesn't. work. After imitating this emoji for some time , you try analysing how you might get a neighbor in the graph. You notice from the small cases that the positions of $1$ and $k$ are very restrictive since they must map to either $1$ or $2$, and $k$ or $k-1$. Due to the pairing argument we already used, it makes sense to look at what happens with the whole pair $(1,2)$. Either it gets mapped to itself—flipped or not—or the $1$ is fixed and then $2$ and $3$ are switched. You try thinking about how to prevent this behavior. In the first case, you're pretty much left with the problem for $k-2$ so you can deal with it inductively. In the other case not so much (this is precisely what gave me a headache and made me stop my mock ). Turns out it's not that difficult since the answer of $\frac{k!}{2^{\frac k2}}$ tells us we need to halve the probability of selecting a permutation anyway, so we can just banish $(123)\to (132)$ by forcing the induced permutation on $(123)$ to be even. To recapitulate what has already been said: We want the induced permutation on $(3,\dots,k)$ to be a solution in the $k-2$ case, and the induced permutation on $(1,2,3)$ to be even. This gives the desired answer by induction.