BMO 2019 Shortlist

With 100 replaced by $N$, the answer is $C=C(N)=N-1$. Throughout, we will say that the members of a couple have the same.

$N=2$: We use this as a base case for induction for both bounds. Up to labelling, there is one trivial initial order, and two non-trivial ones, namely $$1,1,2,2;1,2,2,1;1,2,1,2.$$ The brackets indicate how to arrive at a suitable final ordering with one step. Obviously one step is necessary in the second and third cases.

Upper bound: First we show $C(N)\le N-1$, by induction. The base case $N=2$ has already been seen. Now suppose the claim is true for $N-1$, and consider an initial arrangement of $N$ couples. Suppose the types of the left-most couples in line are $a$ and $b$. If $a\ne b$, then in the first step, swap the $b$ in place two with the other person with type $a$. If $a=b$, skip this. In both cases, we now have $N-1$ couples distributed among the final $2N-2$ places, and we know that $N-2$ steps suffices to order them appropriately, by induction. So $N-1$ steps suffices for $N$ couples.

Lower bound: We need to exhibit an example of an initial order for which $N-1$ steps are necessary. Consider $$A_N:=1,2,2,3,3,\dots ,N-1,N-1,N,N,1.(1)$$ Proceed by induction, with the base case $N=2$ trivial. Suppose there is a sequence of at most $N-2$ steps which works. In any suitable final arrangement, a given type must be in positions (odd, even), whereas they start in positions (even, odd). So each type must be involved in at least one step. However, each step involves at most two types, so by the pigeonhole principle, at least four types are involved in at most one step. Pick one such type $a\ne 1$. The one step involving $a$ must be one of $$\dots ,?,a,a,?,\dots \dots ,?,a,a,?,\dots$$ Neither of these steps affects the relative order of the $2N-2$ other people. So by ignoring this step involving the $a$, we have a sequence of at most $N-3$ steps acting on the other $2N-2$ people which appropriately sorts them. By induction, this is a contradiction. $\square$

Alternative lower bound I: Consider the graph with vertices given by pairs of positions $\{(1,2),(3,4),\dots ,(2N-1,2N)\}$. We add an edge between pairs of (different) vertices if we ever swap two people in places corresponding to those vertices. In particular, at the end, the two people with type $k$ end up in places corresponding to a single vertex. Suppose we start from the ordering (1) and have some number of steps leading to an ordering where everyone is next to their partner. Then, in the induced graph, there is a path between the vertices corresponding to the places $(2k-3,2k-2)$ and $(2k-1,2k)$ for each $2\le k\le N$, and also between $(1,2)$ and $(2N-1,2N)$. In other words, the graph is connected, and so must have at least $N-1$ edges. $\square$

Alternative lower bound II: Consider a bipartite multigraph with vertex classes $(v_1,\dots ,v_n)$ and $(w_1,\dots ,w_n)$. Connect $v_i$ to $w_j$ if a person of type $j$ is in positions $(2i-1,2i)$ (if both positions are taken by the type $j$ couple, then add two edges). Each step in the dance consists of replacing edges $E=\{v_a\leftrightarrow w_c,v_b\leftrightarrow w_d\}$ with $E^{\prime }=\{v_a\leftrightarrow w_d,v_b\leftrightarrow w_c\}$. However, both before and after the step, the number of components in the graph which include $\{v_a,v_b,w_c,w_d\}$ is either one or two. The structure of other components which do not include these vertices is unaffected by the move. Therefore, the number of connected components increases by at most 1 in each step. Starting from configuration (1), the graph initially consists of a single (cyclic) component, so one requires at least $n-1$ steps to get to the final configuration for which there are $n$ connected components. $\square$