In every row of a grid $100 \times n$ is written a permutation of the numbers $1,2 \ldots, 100$. In one move you can choose a row and swap two non-adjacent numbers with difference $1$. Find the largest possible $n$, such that at any moment, no matter the operations made, no two rows may have the same permutations.
Problem
Source: All-Russian MO 2023 Final stage 11.3
Tags: combinatorics
R8kt
23.04.2023 16:58
The answer is 2^99. So the ideas is rather than moving the numbers, we fix them, and move their places in the row.
beOnDrag
23.04.2023 19:19
For $a, b \in \mathbb R$, we define $s(a,b)=-1$ if $a<b$ and $s(a,b)=1$ if $a>b$. The key observation is that: two permutations $(a_1,\cdots,a_n)$ and $(b_1,\cdots,b_n)$ can be made equal if and only if $s(a_i,a_{i+1})=s(b_i,b_{i+1})$ for all $i=1,2,\cdots,n-1$. The proof is not hard.
S.Das93
23.04.2023 19:37
Either I'm missing something, or is it trivial that since we are performing the switching operation on each interval between rows, there must be a maximum of $2^{100-1}=2^{99}$ permutations?
alinazarboland
24.04.2023 10:11
Here's an sketch: Consider $99$ pairs $i,i+1$ for $99 \geq i \geq 1$.Now consider the initial form of any permutation.Some of the $99$ pairs can be switched and some of them cannot which makes it $2^{99}$ possibilities. But clearly permutations with the same set of switchable pairs can be transformed to each other so we can't have more than $2^{99}$ permutations. And the construction can be easily made inductively.
Chronostutter
31.05.2023 14:11
Sorry but I may be confused, why is it that "permutations with the same set of switchable pairs can be transformed to each other"? For example, 125634 and 213465 both have switchable pairs (2,3) and (4,5), but 1is fixed on its position, which means these two cannot be transformed to each other.
ChanandlerBong
18.06.2023 15:53
Here is a sketch of my solution. The answer is $2^{n-1}$ Notice that if one can make several operations that turns one permutation $\sigma$ into $\pi$, one can also turn $\pi$ into $\sigma$, therefore this so called operation actually defines an equivalence relation $\sim$ on the symmetric group $S_n$. Define a mapping $\Psi:S_n\to \{+1,-1\}^n$, for any permutation $\sigma \in S_n$, $ \Psi (\sigma )=(\textbf{sgn}(\sigma (1)-\sigma(2)),\dots ,\textbf{sgn}(\sigma(n-1)-\sigma (n))$. The key observation is that the operation does not change the output of $\Psi$, i.e. if $\sigma \sim \pi$, then $\Psi(\sigma)=\Psi(\pi)$, thus there are at least $2^{n-1}$ equivalence classes. It is a bit trickier to prove that if two permutations have the same output in $\Psi$, they must be equivalent. Here is a hint (it makes the solution more intuitive), consider the reverse permutations and the operation one can make on them. Now the rule becomes to swap two adjacent numbers with difference larger than 1. Try to swap 1 to as in the front as possible, then you would notice that a nice induction kills the problem.
starchan
04.10.2023 20:08
very nice problem solved with Mr Kanav
Make an undirected graph $G$ on $100!$ vertices, one for each permutation of $[100]$ and connect a permutation $\tau_1$ to a permutation $\tau_2$ if it is possible to make a move on $\tau_1$ to convert it into $\tau_2$ (and vice versa, since the operation is reversible).
Observe that we simply wish to count the number of connected components of $G$. To do this, first to each permutation $\tau$ we assign the unique string $S(\tau) = s_1s_2 \dots s_{99}$ of length $99$, consisting of characters $\{<, >\}$ for which the statements: \[\tau_i ~~s_i ~~\tau_{i+1}\]are all true for $1 \leq i \leq 99$.
Claim: If $u, v$ are connected then $S(u) = S(v)$.
Proof: Suppose we swap numbers $m, m+1$ to convert $u \mapsto v$. Since $m$ is surrounded by numbers either $\geq m+2$ or $\leq m-1$ changing $m$ to $m+1$ does not affect $S(v)$ in that character. Analogously, since $m+1$ is surrounded by numbers either $\geq m+2$ or $\leq m-1$ in this position too, $S(v)$ remains unchanged. Note that we used the fact that $m, m+1$ are not adjacent here. $\square$
It follows that over each connected component of $G$, the string $S(u)$ is fixed. We next show that any two permutations $\tau_1, \tau_2$ with the same $S$-value are in the same connected component. For each string $s_1s_2\dots s_{99} \in \{<, >\}^{99}$ we assign a permutation $\tau(s)$ using the following algorithm:
Step 1: Initialise a variable $n = 1$.
Step 2: Consider the longest string of $>$ chararcters. Suppose it has length $m$ (this may be zero).
Step 3: Assign the next $m+1$ values unassigned to $\tau$ (in left to right order) the values \[m+n, m+n-1, \dots, n\]
Step 4: Replace $n$ with $n+m+1$. If $n \geq 101$, stop. Otherwise, go to Step 2.
It's easy to see that the above algorithm creates a valid permutation with its $S$-value being $s_1s_2 \dots s_{99}$.
We now show that each permutation $\sigma$ of $[100]$ can be converted to $\tau\left(S(\sigma)\right)$ after a sequence of operations. Fix any permutation $\sigma$ and consider doing the following:
If there are two integers $m, m+1$ such that $m+1$ appears before $m$ in $\sigma$ and are not adjacent, we swap them.
Else, we stop.
First, observe that the above cannot go on indefinitely. Indeed, if it did some number in $[100]$ would move back infinitely often, impossible since there's only $100$ places it could've been in. Thus we stop at some stage and $\sigma$ has become some new permuation $\sigma'$.
Claim: $\sigma' \equiv \tau\left(S(\sigma)\right)$
Proof: We will be inducting. It's a bit finicky to exactly define what we are inducting on now, after all the previous terminology but it will be clear in just a while. Let the location of $1$ in the permutation $\sigma'$ be in the $i$th position. Now $2$ is either after $1$ or before $1$. Let us suppose that $2, 3, \dots, m$ all lie to the left of $1$ consecutively with $m$ maximal. We show that $\sigma'$ starts with $m$ and thus we may induct down to the permutation after $1$ by shifting all the values down by $m$. Suppose there are numbers before $m$ and let $n$ be the smallest among them. Then $n-1$ lies to the right of the $[m, \dots, 1]$ block and we could have swapped $n$ for $n-1$; a contradiction. Thus we can induct down and we prove the claim.
With the two Claims in hand, it is clear that each connected component of $G$ is described by the string value each vertex has. It follows that the number of connected components of $G$ is the number of strings in $\{<, >\}^{99}$, which is $2^{99}$ and our final answer. $\square$
IAmTheHazard
04.10.2023 21:34
The answer is $2^{99}$. We are clearly being asked to find the number of equivalence classes under the (reversible) operation of repeated swapping. To prove that there are at least $2^{99}$ equivalence classes, note that any swap on $a_1,\ldots,a_{100}$ preserves the values of $\mathrm{sgn}(a_i-a_{i+1})$ for all $1 \leq i \leq 99$. There are $2^{99}$ possibilities for these values, hence at least this many classes. To prove that there are at most $2^{99}$ classes, take an arbitrary permutation and successively perform swaps that decrease its lexicographic order. This eventually terminates, and when this occurs, we must have $a_i+1 \in \{a_{i-1},a_{i+1},a_{i+2},\ldots,a_{100}\}$ for all $i$ with $a_i \neq 100$. In particular, starting from the end, the sequence should have the form $k_1,k_1+1,\ldots,100$ for some $k_1$. The next term is $k_2<k_1$, and then the terms $k_2,k_2+1,\ldots,k_1-1$ are uniquely determined, and so on. In general we should get (viewing from left to right) an ascending sequence of "down-slopes". It is clear that the choice of ending points on these "down-slopes" uniquely determines them, and there are $2^{99}$ such choices (since the last term must be an endpoint), so we're done. $\blacksquare$ For explicitness: if we replace $100$ by $6$, then the permutation formed by choosing endpoints of "down-slopes" at $2,3,6$ is $2,1,3,6,5,4$ (formed by constructing in reverse, starting from the end).