There are $n$ husbands and wives at a party in the palace. The husbands sit at a round table, and the wives sit at another round tables. The king and queen (not included in the $n$ couples) are going to shake hands with them one by one. Assume that the king starts from a man, and the queen starts from his wife. Consider the following two ways of shaking hands: (i) The king shakes hands with the men one by one clockwise. Each time when the king shakes hands with a man, the queen moves clockwise to his wife and shakes hands with her. Assume that at last when the king gets back to the man he begins with, the queen goes around the table $a$ times. (ii) The queen shakes hands with the women one by one clockwise. Each time when the queen shakes hands with a woman, the king moves clockwise to her husband and shakes hands with him. Assume that at last when the queen gets back to the woman she begins with, the king goes around the table $b$ times. Determine the maximum possible value of $|a-b|$.
Problem
Source: 2018 Taiwan TST Round 1
Tags: combinatorics, Taiwan TST, Taiwan
30.05.2020 19:59
With Luke Robitaille and Yannick Yao. For $n=1$ the answer is $0$, so assume $n > 1$ from here. Label the couples $0, 1, \dotsc, n-1$ so that the king and queen always start with couple $0$ and the men are seated clockwise in the order $0, 1, \dotsc, n-1$. Let the women are seated clockwise in the order $0, \pi(1), \dotsc, \pi(n-1)$ where $\pi$ is a permutation of $\{1, 2, \dotsc, n-1\}$. We make the following observations: $a-1$ is equal to the number of indices $i$ with $\pi^{-1}(i) > \pi^{-1}(i+1)$ (each such index corresponds to an instance where the queen passes by woman $0$ without shaking hands). $b-1$ is equal to the number of indices $i$ with $\pi(i) > \pi(i+1)$ (each such index corresponds to an instance where the king passes by man $0$ without shaking hands). Let $s$ and $t$ be the maximum lengths of an increasing and decreasing subsequence of $\pi$, respectively. Claim 1. $t\leq a\leq n-s$. Proof. A decreasing subsequence $\pi(i_1), \dotsc, \pi(i_t)$ of length $t$ in $\pi$ corresponds to a decreasing subsequence $\pi^{-1}(\pi(i_t)), \dotsc, \pi^{-1}(\pi(i_1))$ of length $t$ in $\pi^{-1}$. Therefore $\pi^{-1}$ decreases at least $t-1$ times, so $a-1\geq t-1$. On the right hand side, an increasing subsequence of length $s$ in $\pi$ corresponds to an increasing subsequence of length $s$ in $\pi^{-1}$. Since $\pi^{-1}$ increases at least $s-1$ times, it decreases at most $n-2-(s-1)=n-1-s$ times. Therefore $a-1\leq n-1-s$. Claim 2. $t\leq b\leq n-s$. Proof. If there is a decreasing subsequence of length $t$, then $\pi$ must decrease at least $t-1$ times. Therefore $a-1\geq t-1$. On the right hand side, if there is an increasing subsequence of length $s$, then $\pi$ must increase at least $s-1$ times. Therefore $a-1\leq n-2-(s-1)=n-1-s$. Combining the two claims yields \[|a-b|\leq n-(s+t).\]Claim 3. $st\geq n-1$. Proof. This is classical. Label the $i$th element of $\pi$ with $(s_i, t_i)$ where $s_i$ is the length of the longest increasing subsequence of $\pi$ ending at the $i$th element and $t_i$ is the length of the longest decreasing subsequence of $\pi$ ending at the $i$th element. This defines an injective map $\{1, 2, \dotsc, n-1\}\to \{1, 2, \dotsc, s\}\times\{1, 2, \dotsc, t\}$. We can compute that the minimum value of $s+t$ subject to $st\geq n-1$ is $\left\lceil 2\sqrt{n-1}\right\rceil$, so \[|a-b|\leq n-\left\lceil 2\sqrt{n-1}\right\rceil.\]Finally, we provide a construction. Choose $s$ and $t$ so that $st\geq n-1$ and $s+t$ is minimal. Let \[\pi = (t, 2t, \dotsc, st, t-1, 2t-1, \dotsc, st-1, \dotsc 1, t+1, \dotsc, st-t+1),\]except with all elements greater than $n-1$ removed. (Related problem: ELMO 2016/3.)
18.05.2022 18:42
Label the husbands in clockwise order 1, ..., n and their wives in order $\sigma(1), \cdots, \sigma(n)$. Then observe $a=\#_{1\le i\le n} \sigma(i+1)<\sigma(i)$ and $b=\#_{1\le i\le n} \sigma^{-1}(i+1)<\sigma^{-1}(i)$ The answer is $n-\lceil 2\sqrt{n-1} \rceil$ if $n\ge 2$ and $0$ otherwise. WLOG $a<b$. The key claim is $a(n-b)\ge n-1$ We can rewrite this as $a$ "chains": $$ \sigma(x_1)< \sigma(x_1+1)< \cdots < \sigma(x_2-1)$$ $$\sigma(x_2) < \sigma(x_2+1) < \cdots < \sigma(x_3-1)$$ All the way to $x_a$ to $n+x_1-1$, where $x_1<x_2<\cdots<x_a$ We need to show there are at least $\frac{n-1}{a}$ indices $j$ where $\sigma^{-1}(j+1)<\sigma^{-1}(j)$ By incrementing a value to every $x_i$ (mod n) but not changing the $\sigma$ values, $b$ doesn't change. This basically changes $\sigma^{-1} \to \sigma^{-1}+c$ and induct on $c$ to see $a$ doesn't change.) we may assume $x_1=1$. Suppose $n-b=m$ and $\sigma(x_t)=1$. This means each chain above $x_t$'s chain has length at most $m$, or observe $\sigma(x_u) < \sigma(x_u+1) < \cdots < \sigma(x_{u+1}-1) < \sigma(x_t)$ forces $n-b\ge m+1$. Similarly $x_t$'s chain has at most length $m+1$, the end! Will post construction later.