Chinese Mathematical Olympiad

(1) For an intuitive understanding, place numbers $1,2,\dots ,p$ equidistantly in a clockwise direction on the circumference of a circle with a perimeter exactly equal to $p$. Then $r(x,y)$ is precisely the distance from $x$ to $y$ in a clockwise direction. For an $m$-element subset $A=\{x_1,x_2,\dots ,x_m\}$ of $\Omega$ (with elements arranged from smallest to largest), we have $$f(A)=\sum _{x,y\in A}r(x,y{)}^2=\sum _{k=1}^{m-1}\sum _{i=1}^{m}r(x_i,x_{i+k}{)}^2.$$ Here, indices are considered modulo $m$. For $k=1,2,\dots ,m-1$, notice that ${\sum }_{i=1}^{m}r(x_i,x_{i+k})=kp$, as the $m$ arcs from $x_1$ to $x_{1+k}$, from $x_2$ to $x_{2+k}$, $\dots$, from $x_m$ to $x_k$ can be recombined to form $k$ circles. By the AM-GM inequality, the minimum value of the partial sum $S_k={\sum }_{i=1}^{m}r(x_i,x_{i+k}{)}^2$ is obtained when each $d(x_i,x_{i+k})=\lfloor \frac{kp}{m}\rfloor$ or $\lceil \frac{kp}{m}\rceil$. For all $S_k$ to reach their minimum values, it is equivalent to, for any $i,j=1,2,\dots ,m$, $$\left|x_j-x_i-\frac{(j-i)p}{m}\right|<1.$$ That is, the differences between any two numbers in the set $D=\{x_1-\frac{p}{m},x_2-\frac{2p}{m},\dots ,x_m-\frac{mp}{m}\}$ are less than 1. (In other words, this requires $x_1,\dots ,x_m$ to be almost equidistantly distributed on the circle.) Since multiplying the numbers in $D$ by $m$ yields distinct integers, we can set $D=\{\frac{r}{m},\frac{r-1}{m},\dots ,\frac{r-(m-1)}{m}\}$. Thus for $k=1,2,\dots ,m$, $x_k$ is the only integer among $\frac{kp+r}{m},\frac{kp+r-1}{m},\dots ,\frac{kp+r-(m-1)}{m}$, i.e., $x_k=\lfloor \frac{kp+r}{m}\rfloor$. From $x_1\ge 1$ we know $r\ge m-p$, and from $x_m\le p$ we know $r\le m-1$. Therefore, each of the aforementioned partial sums $S_k$ reaches its minimum value if and only if the set $$A=\left\{x_k=\lfloor \frac{kp+r}{m}\rfloor \mid k=1,2,\dots ,m\right\},$$ where $r\in \{m-p,m-p+1,\dots ,m-1\}$. Specifically, at this time $f$ takes its minimum value among all $m$-element subsets, meaning these $A$ are precisely all the $m$-element good subsets. Since every element of a good subset $A$ plus $k$ (modulo $p$) is still a good subset, all $m$-element good subsets are "rotationally equivalent" (they are rotations of $\{\lfloor \frac{kp}{m}\rfloor \mid k=1,\dots ,m\}$).

(2) For convenience of explanation and understanding, we define a graph $G$ with $V=\{1,2,\dots ,p-1\}$ as vertices. If there exists an $a$-element good subset $A$ and a $b$-element good subset $B$ such that $A\subset B$, then we draw a directed edge $a\to b$. Due to the rotational equivalence of good subsets: if some $b$-element good subset contains an $a$-element good subset, then every $b$-element good subset contains some $a$-element good subset, and every $a$-element good subset is also contained in some $b$-element good subset. (Clearly, graph $G$ forms a poset, i.e., if $a\to b,b\to c$ then $a\to c$). Therefore, the problem transforms into considering the chains $a_1\to a_2\to \cdots \to a_L$ in graph $G$, (where $L$ is the length of the chain).

We prove the following conclusions:

Conclusion 1: The complement $A^c$ of any $m$-element good subset $A$ is also a good subset. Proof of Conclusion 1: Observe the following identity: $$\begin{gathered} f(A)-f(A^c)=\left(\sum _{x\in A}\sum _{y\in \Omega }r(x,y{)}^2-\sum _{x\in A}\sum _{y\in A^c}r(x,y{)}^2\right)-\left(\sum _{x\in \Omega }\sum _{y\in A^c}r(x,y{)}^2-\sum _{x\in A}\sum _{y\in A^c}r(x,y{)}^2\right) \\ =\sum _{x\in A}\sum _{y\in \Omega }r(x,y{)}^2-\sum _{x\in \Omega }\sum _{y\in A^c}r(x,y{)}^2=|A|\times \sum _{k=0}^{m-1}{\left(\frac{k}{m}\right)}^2-\sum _{k=0}^{m-1}{\left(\frac{k}{m}\right)}^2\times |A^c|, \end{gathered}$$ i.e., $f(A)-f(A^c)$ is a constant value. Therefore, $f(A)$ reaching its minimum is equivalent to $f(A^c)$ reaching its minimum. Thus, a good subset $A\subset B$ is also equivalent to good subset $B^c\subset A^c$, i.e., in graph $G$ there is an edge $a\to b$ if and only if there is an edge $(p-b)\to (p-a)$.

Conclusion 2: When $m<\frac{p}{2}$, any $m$-element good subset $A$ can be contained within a rotation of its complement $A^c$, i.e., graph $G$ has an edge $m\to (p-m)$. Proof of Conclusion 2: Take the $2m$-element good subset $C=\{\lfloor \frac{kp}{2m}\rfloor \mid k=1,2,\dots ,2m\}$, then $$A=\left\{y_k=x_{2k}=\lfloor \frac{kp}{m}\rfloor \right\}\text{and}B=\left\{z_k=x_{2k-1}=\lfloor \frac{kp+\left(-\frac{p+1}{2}\right)}{m}\rfloor \right\}$$ are both $m$-element good subsets, and $B^c$ is a $p-m$-element good subset. Thus $A\subset B^c$. Alternate proof of Conclusion 2: Since $m<\frac{p}{2}$, $A$ and $A+1=\{x+1\mid x\in A\}$ do not intersect. Hence $A\subset (A+1{)}^c$. Conclusion 2 holds.

The aforementioned symmetry of graph $G$ means that we only need to consider the longest chain from 1 to some number $<\frac{p}{2}$. This is because for a chain $a_1\to a_2\to \cdots \to a_L$, let $a_k<\frac{p}{2}$, $a_{k+1}>\frac{p}{2}$, then we can form two new chains $$\begin{array}{rl}{a}_1& \to \cdots \to a_k\to (p-a_k)\to \cdots \to (p-a_1)\text{(length 2k)},\\ p-a_L& \to \cdots \to p-a_{k+1}\to a_{k+1}\to \cdots \to a_L\text{(length 2L-2k)}.\end{array}$$ At least one of these has length $\ge L$. Therefore, we only need to consider "self-symmetric" chains.

Conclusion 3: When $a$ divides $b$, there is an edge $a\to b$, because the good subset $$B=\{x_k=\lfloor \frac{kp}{b}\rfloor ,k=1,2,\dots ,b\}\supset A=\{y_k=x_{k\times \frac{b}{a}}=\lfloor \frac{kp}{a}\rfloor ,k=1,2,\dots ,a\}.$$ From this, we know that when $2^u<p<2^{u+1}$, there is always a chain of length $2u$ $$1\to 2\to 4\to \cdots \to 2^{u-1}\to (p-2^{u-1})\to (p-2^{u-2})\to \cdots \to (p-2)\to (p-1).(2)$$ If the length of a chain $L>2u$, by symmetry, we may assume $a_{u+1}<\frac{p}{2}$. Next, we consider the necessary conditions for an edge $a\to b$ in graph $G$ when $a<b<\frac{p}{2}$.

Conclusion 4: When $a<b<\frac{p}{3}$, if an $a$-element good subset $A$ is contained in a $b$-element good subset $B$, i.e., $a\to b$, then $a$ must be a divisor of $b$. Proof of Conclusion 4: Without loss of generality, assume good subset $B=\{x_k=\lfloor \frac{kp}{b}\rfloor ,k=1,2,\dots ,b\}$ contains good subset $A=\{y_j=x_{k_j},j=1,2,\dots ,a\}$. If $k_1,k_2,\dots ,k_a$ are not equally spaced, for example, $k_2-k_1>k_3-k_2$, then the difference between adjacent elements in $A$ is $$\begin{gathered} y_2-y_1=x_{k_2}-x_{k_1}\ge \lfloor \frac{(k_2-k_1)p}{b}\rfloor \ge \lfloor \frac{(k_2-k_1-1)p}{b}\rfloor +\lfloor \frac{p}{b}\rfloor \\ \ge \lfloor \frac{(k_3-k_2)p}{b}\rfloor +3\ge x_{k_3}-x_{k_2}+2=y_3-y_2+2, \end{gathered}$$ which contradicts the fact that $A$ is a good subset. Therefore, $a$ must be a divisor of $b$.

Conclusion 5: When $\frac{p}{4}<a<b<\frac{p}{2}$, except when $p\equiv 3(\mathrm{mod}4)$ with an edge $\frac{p+1}{4}\to \frac{p-1}{2}$, there is no edge between $a$ and $b$. Proof of Conclusion 5: From Conclusion 4, we know at this point $\frac{p}{3}<b<\frac{p}{2}$, otherwise $b<\frac{p}{3}$ and is a multiple of $a$, which is impossible. As in the proof of Conclusion 4, assume good subset $B=\{x_k=\lfloor \frac{kp}{b}\rfloor ,k=1,2,\dots ,b\}$ contains good subset $A=\{y_j=x_{k_j},j=1,2,\dots ,a\}$. Let the interval in $B$ be $h_k=x_{k+1}-x_k=\lfloor \frac{kp+p}{b}\rfloor -\lfloor \frac{kp}{b}\rfloor \in \{2,3\}$. Hence, there exists an interval in $A$ $y_{j+1}-y_j\ge x_{k+2}-x_k\ge 4$, so $|A|=a<\frac{p}{3}$, i.e., intervals in $A$ $g_j=y_{j+1}-y_j\in \{\lfloor \frac{p}{a}\rfloor ,\lceil \frac{p}{a}\rceil \}=\{3,4\}$. Clearly, the sequence $\mathbf{h}=(h_1,h_2,\dots ,h_b)$ is obtained from $\mathbf{g}=(g_1,g_2,\dots ,g_a)$ by replacing each 4 with two consecutive 2s. If the sequence $\mathbf{h}$ contains at least two 3s, consider the number of 2s between each pair of adjacent 3s. These numbers can differ by at most 1 (otherwise, in $\mathbf{h}$ there is a segment with $t+2$ consecutive 2s, another with at most $t$ 2s between two 3s, with a total difference of at least 2, contradicting $B$ being a good subset), and all these numbers are even, so they are all equal. This makes the sequence $\mathbf{h}$ have a smaller period, contradicting the total sum of $\mathbf{h}$ being the prime number $p$. Therefore, $\mathbf{h}$ contains one 3 and $b-1$ 2s, i.e., $p=2b+1$. The sequence $\mathbf{g}$ contains one 3 and $a-1$ 4s, i.e., $p=4a-1$. In this case, take $$A=\{1,5,9,\dots ,p-2\}\subset B=\{1,3,5,\dots ,p-2\}$$ to prove Conclusion 5.

Combining Conclusions 4 and 5, we know that when $2^u<p<2^{u+1}$, for any chain $a_1\to a_2\to \cdots \to a_L$, the sequence $a_1,a_2,a_3,\dots$ before $\frac{p}{4}$ multiplies by several times each step, so there are at most $u-1$ numbers (since $\frac{p}{4}<2^{u-1}$), thus $a_u>\frac{p}{4}$. If $a_{u+1}<\frac{p}{2}$, then necessarily $a_u=\frac{p+1}{4}$, $a_{u+1}=\frac{p-1}{2}$, in which case only $a_u=2^{u-1}$ (otherwise $a_u\ge 3\times 2^{u-2}>\frac{p-1}{4}$), i.e., $p=2^{u+1}-1$.

In summary, $L_{\max }=2\times \lfloor {\log }_2(p+1)\rfloor$. Thus, when $2^u<p<2^{u+1}-1$, $L\le 2u$, with equality in chain (2). When $p=2^{u+1}-1$, $L\le 2(u+1)$, with equality in the following chain: $$1\to 2\to \cdots \to 2^{u-1}\to 2^u-1\to 2^u\to (p-2^{u-1})\to (p-2^{u-2})\to \cdots \to (p-2)\to (p-1).$$

---

Alternative solution.

The characterization of good subsets is similar to part (1) in Solution 1. The following discussion simplifies the subsequent proof. Notice that $$\lfloor \frac{kp}{m}\rfloor \cdot m\equiv \{\frac{kp}{m}\}\cdot m\mathrm{mod}p.$$ And when $k=0,1,\dots ,m-1$, $\{\frac{kp}{m}\}$ takes all values from $0,1,\dots ,m-1$. Hence, modulo $p$, $\{m\lfloor \frac{kp}{m}\rfloor \}$ is equal to $\{0,-1,\dots ,-(m-1)\}$. Due to the uniqueness of rotation, any $m$-element good subset multiplied by $m$ (in the sense of modulo $p$) consists of consecutive $m$ numbers. Conversely, if an $m$-element subset multiplied by $m$ consists of consecutive $m$ numbers, it must be an $m$-element good subset. Let $r$ be the modular multiplicative inverse of $m$ modulo $p$, then $\{\lfloor \frac{kp}{m}\rfloor \}\equiv \{0,-r,\dots ,-(m-1)r\}\mathrm{mod}p$. Therefore, any $m$-element set is a good subset if and only if it can be written as $\{a,a+r,\dots ,a+(m-1)r\}\mathrm{mod}p$.

The following steps are similar to Conclusions 1–5 in Solution 1, but the proofs are relatively simpler.

Conclusion 1: The complement of any $m$-element good subset is a $p-m$-element good subset. Proof of Conclusion 1: Based on the above characterization, assume the $m$-element good subset is $\{a,a+r,\dots ,a+(m-1)r\}$ (in the sense of modulo $p$), then its complement can be written as $\{a-r,a-2r,\dots ,a-(p-m)r\}$ modulo $p$. Since the modular multiplicative inverse of $p-m$ modulo $p$ is $-r$ modulo $p$, the set $\{a-r,a-2r,\dots ,a-(p-m)r\}$ is a good subset.

Conclusion 2: If $m<\frac{p}{2}$, then any $m$-element good subset is contained in some $p-m$-element good subset. Proof of Conclusion 2: Without loss of generality, assume the $m$-element good subset is $\{a,a+r,\dots ,a+(m-1)r\}$ (in the sense of modulo $p$), then it is contained in the $p-m$-element good subset $\{a+(p-m-1)r,a+(p-m-2)r,\dots ,a\}$.

Conclusion 3: If $km<p$, then any $m$-element good subset is contained in some $km$-element good subset. Proof of Conclusion 3: Assume the $m$-element good subset is $A=\{a,a+r,\dots ,a+(m-1)r\}$ (in the sense of modulo $p$). Let $s$ be the modular multiplicative inverse of $km$ modulo $p$, so $ks\equiv r(\mathrm{mod}p)$. Then $A$ is contained in the $km$-element good subset $B=\{a,a+s,\dots ,a+(km-1)s\}$.

Conclusion 4: If $p\equiv 3(\mathrm{mod}4)$, then any $\frac{p+1}{4}$-element good subset is contained in some $\frac{p-1}{2}$-element good subset. Proof of Conclusion 4: Note that the modular multiplicative inverse of $\frac{p+1}{4}$ modulo $p$ is 4, and for $\frac{p-1}{2}$ modulo $p$ it is -2. Suppose the $\frac{p+1}{4}$-element good subset is $\{a,a+2,\dots ,a+p-3\}$, then it is contained in the $\frac{p-1}{2}$-element good subset $\{a+p-3,a+p-5,\dots ,a+2,a\}$.

Conclusion 5: If $1\le n<m\le \frac{p}{2}$, and some $m$-element good subset is contained in some $n$-element good subset, then $m\ge 2n-1$, and equality holds if and only if $n=\frac{p+1}{4}$ and $m=\frac{p-1}{2}$.

Proof of Conclusion 5: Multiply all numbers by $m$. Then, in the sense of modulo $p$, an $m$-element good subset becomes a sequence of consecutive $m$ numbers (since the original common difference was the modular inverse of $m$ modulo $p$), and the $n$-element good subset also becomes an arithmetic sequence $T$, with a common difference congruent to $\frac{m}{n}$ modulo $p$, i.e., not congruent to $\pm 1$ modulo $p$. Assume the transformed $m$-element good subset is $\{0,1,\dots ,m-1\}$, with the first term $a$ of $T$ in $\{0,1,\dots ,m-1\}$, and let the common difference be $\beta$, where $|\beta |<\frac{p}{2}$. Note that $p-(m-1)>\frac{p}{2}$, so every term of $T$ must be in $\{0,1,\dots ,m-1\}$, hence $m=(m-1)+1\ge (n-1)|\beta |+1\ge 2n-1$. When equality holds, $|\beta |=2$ must be true, thus $\frac{m}{n}\equiv \pm 2(\mathrm{mod}p)$, meaning $2n-1\equiv \pm 2n(\mathrm{mod}p)$. As $n\le \frac{m+1}{2}\le \frac{p+1}{4}$, the only possibility is $n=\frac{p+1}{4}$ and $m=\frac{p-1}{2}$.

Now returning to the original problem, for any chain of good subsets $A_1\subset A_2\subset \cdots \subset A_L$, let $|A_q|<\frac{p}{2}$ and $|A_{q+1}|>\frac{p}{2}$. By Conclusion 5, we have $$\frac{p+1}{2}\ge 2|A_{q-1}|\ge 2^2|A_{q-2}|\ge \cdots \ge 2^{q-1}|A_1|=2^{q-1}.$$ Thus, $q\le \lfloor {\log }_2(p+1)\rfloor$. By Conclusion 1, the chain of complements $A_L^c\subset A_{L-1}^c\subset \cdots \subset A_{q+1}^c$ also forms a chain of good subsets, and similarly, we find $L-q\le \lfloor {\log }_2(p+1)\rfloor$. Therefore, $L\le 2\lfloor {\log }_2(p+1)\rfloor$.

When $2^q<p+1<2^{q+1}$, by Conclusions 1, 2, and 3, there exists a chain of good subsets $A_1\subset A_2\subset \cdots \subset A_{2q}$, where $|A_i|=2^{i-1}$, $|A_{2q+1-i}|=p-2^{i-1}$, for $i=1,2,\dots ,q$.

When $p=2^q-1$, by Conclusions 1, 2, 3, and 4, there exists a chain of good subsets $A_1\subset A_2\subset \cdots \subset A_{2q}$, where $|A_i|=2^{i-1}$, $|A_{2q+1-i}|=p-2^{i-1}$, for $i=1,2,\dots ,q-1$, $|A_q|=2^{q-1}-1$, and $|A_{q+1}|=2^{q-1}$.

In summary, the maximum $L$ sought is $2\lfloor {\log }_2(p+1)\rfloor$.