Maths Olympiad Prep

Library / /15 of 18

Number theory Difficulty 7.7 National olympiad, round 2 Prove it China

Fix a prime number p5p \ge 5, and put Ω={1,2,,p}\Omega = \{1, 2, \dots, p\}. For any x,yΩx, y \in \Omega, define
r(x,y)={yx,if yx,yx+p,if y<x. r(x, y) = \begin{cases} y - x, & \text{if } y \ge x, \\ y - x + p, & \text{if } y < x. \end{cases}
For a nonempty subset AA of Ω\Omega, define
f(A)=xAyA(r(x,y))2. f(A) = \sum_{x \in A} \sum_{y \in A} (r(x, y))^2.
We say that a subset AA of Ω\Omega is *good* if 0<A<p0 < |A| < p and for any subset BB of Ω\Omega with B=A|B| = |A|, we have f(B)f(A)f(B) \ge f(A).
Determine the maximal positive integer LL, such that there exist pairwise distinct good subsets A1,A2,,ALA_1, A_2, \dots, A_L of Ω\Omega such that A1A2ALA_1 \subset A_2 \subset \dots \subset A_L.

Solutions — 2

Solution 1

(1) For an intuitive understanding, place numbers 1,2,,p1, 2, \dots, p equidistantly in a clockwise direction on the circumference of a circle with a perimeter exactly equal to pp. Then r(x,y)r(x, y) is precisely the distance from xx to yy in a clockwise direction.
For an mm-element subset A={x1,x2,,xm}A = \{x_1, x_2, \dots, x_m\} of Ω\Omega (with elements arranged from smallest to largest), we have
f(A)=x,yAr(x,y)2=k=1m1i=1mr(xi,xi+k)2. 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 mm.
For k=1,2,,m1k = 1, 2, \dots, m-1, notice that i=1mr(xi,xi+k)=kp\sum_{i=1}^{m} r(x_i, x_{i+k}) = kp, as the mm arcs from x1x_1 to x1+kx_{1+k}, from x2x_2 to x2+kx_{2+k}, \dots, from xmx_m to xkx_k can be recombined to form kk circles. By the AM-GM inequality, the minimum value of the partial sum Sk=i=1mr(xi,xi+k)2S_k = \sum_{i=1}^{m} r(x_i, x_{i+k})^2 is obtained when each d(xi,xi+k)=kpmd(x_i, x_{i+k}) = \lfloor \frac{kp}{m} \rfloor or kpm\lceil \frac{kp}{m} \rceil. For all SkS_k to reach their minimum values, it is equivalent to, for any i,j=1,2,,mi, j = 1, 2, \dots, m,
xjxi(ji)pm<1. \left| x_j - x_i - \frac{(j-i)p}{m} \right| < 1.
That is, the differences between any two numbers in the set D={x1pm,x22pm,,xmmpm}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 x1,,xmx_1, \dots, x_m to be almost equidistantly distributed on the circle.) Since multiplying the numbers in DD by mm yields distinct integers, we can set D={rm,r1m,,r(m1)m}D = \{\frac{r}{m}, \frac{r-1}{m}, \dots, \frac{r-(m-1)}{m}\}. Thus for k=1,2,,mk = 1, 2, \dots, m, xkx_k is the only integer among kp+rm,kp+r1m,,kp+r(m1)m\frac{kp+r}{m}, \frac{kp+r-1}{m}, \dots, \frac{kp+r-(m-1)}{m}, i.e., xk=kp+rmx_k = \lfloor \frac{kp+r}{m} \rfloor. From x11x_1 \ge 1 we know rmpr \ge m-p, and from xmpx_m \le p we know rm1r \le m-1.
Therefore, each of the aforementioned partial sums SkS_k reaches its minimum value if and only if the set
A={xk=kp+rmk=1,2,,m}, A = \left\{ x_k = \left\lfloor \frac{kp+r}{m} \right\rfloor \mid k = 1, 2, \dots, m \right\},
where r{mp,mp+1,,m1}r \in \{m-p, m-p+1, \dots, m-1\}. Specifically, at this time ff takes its minimum value among all mm-element subsets, meaning these AA are precisely all the mm-element good subsets. Since every element of a good subset AA plus kk (modulo pp) is still a good subset, all mm-element good subsets are "rotationally equivalent" (they are rotations of {kpmk=1,,m}\{\lfloor \frac{kp}{m} \rfloor \mid k = 1, \dots, m\}).

(2) For convenience of explanation and understanding, we define a graph GG with V={1,2,,p1}V = \{1, 2, \dots, p-1\} as vertices. If there exists an aa-element good subset AA and a bb-element good subset BB such that ABA \subset B, then we draw a directed edge aba \to b. Due to the rotational equivalence of good subsets: if some bb-element good subset contains an aa-element good subset, then every bb-element good subset contains some aa-element good subset, and every aa-element good subset is also contained in some bb-element good subset. (Clearly, graph GG forms a poset, i.e., if ab,bca \to b, b \to c then aca \to c). Therefore, the problem transforms into considering the chains a1a2aLa_1 \to a_2 \to \dots \to a_L in graph GG, (where LL is the length of the chain).

We prove the following conclusions:

Conclusion 1: The complement AcA^c of any mm-element good subset AA is also a good subset.
*Proof of Conclusion 1:* Observe the following identity:
f(A)f(Ac)=(xAyΩr(x,y)2xAyAcr(x,y)2)(xΩyAcr(x,y)2xAyAcr(x,y)2)=xAyΩr(x,y)2xΩyAcr(x,y)2=A×k=0m1(km)2k=0m1(km)2×Ac, 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|,
i.e., f(A)f(Ac)f(A) - f(A^c) is a constant value. Therefore, f(A)f(A) reaching its minimum is equivalent to f(Ac)f(A^c) reaching its minimum.
Thus, a good subset ABA \subset B is also equivalent to good subset BcAcB^c \subset A^c, i.e., in graph GG there is an edge aba \to b if and only if there is an edge (pb)(pa)(p-b) \to (p-a).

Conclusion 2: When m<p2m < \frac{p}{2}, any mm-element good subset AA can be contained within a rotation of its complement AcA^c, i.e., graph GG has an edge m(pm)m \to (p-m).
*Proof of Conclusion 2:* Take the 2m2m-element good subset C={kp2mk=1,2,,2m}C = \{\lfloor \frac{kp}{2m} \rfloor \mid k = 1, 2, \dots, 2m\}, then
A={yk=x2k=kpm}andB={zk=x2k1=kp+(p+12)m} A = \left\{ y_k = x_{2k} = \left\lfloor \frac{kp}{m} \right\rfloor \right\} \quad \text{and} \quad B = \left\{ z_k = x_{2k-1} = \left\lfloor \frac{kp + \left(-\frac{p+1}{2}\right)}{m} \right\rfloor \right\}
are both mm-element good subsets, and BcB^c is a pmp-m-element good subset. Thus ABcA \subset B^c.
*Alternate proof of Conclusion 2:* Since m<p2m < \frac{p}{2}, AA and A+1={x+1xA}A+1 = \{x+1 \mid x \in A\} do not intersect. Hence A(A+1)cA \subset (A+1)^c. Conclusion 2 holds.

The aforementioned symmetry of graph GG means that we only need to consider the longest chain from 1 to some number <p2< \frac{p}{2}. This is because for a chain a1a2aLa_1 \to a_2 \to \dots \to a_L, let ak<p2a_k < \frac{p}{2}, ak+1>p2a_{k+1} > \frac{p}{2}, then we can form two new chains
a1ak(pak)(pa1)(length 2k),paLpak+1ak+1aL(length 2L-2k). \begin{align*} a_1 &\to \dots \to a_k \to (p-a_k) \to \dots \to (p-a_1) \quad \text{(length 2k)}, \\ p-a_L &\to \dots \to p-a_{k+1} \to a_{k+1} \to \dots \to a_L \quad \text{(length 2L-2k)}.\end{align*}
At least one of these has length L\ge L. Therefore, we only need to consider "self-symmetric" chains.

Conclusion 3: When aa divides bb, there is an edge aba \to b, because the good subset
B={xk=kpb,k=1,2,,b}A={yk=xk×ba=kpa,k=1,2,,a}. 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 2u<p<2u+12^u < p < 2^{u+1}, there is always a chain of length 2u2u
1242u1(p2u1)(p2u2)(p2)(p1).(2) 1 \to 2 \to 4 \to \dots \to 2^{u-1} \to (p-2^{u-1}) \to (p-2^{u-2}) \to \dots \to (p-2) \to (p-1). \quad (2)
If the length of a chain L>2uL > 2u, by symmetry, we may assume au+1<p2a_{u+1} < \frac{p}{2}.
Next, we consider the necessary conditions for an edge aba \to b in graph GG when a<b<p2a < b < \frac{p}{2}.

Conclusion 4: When a<b<p3a < b < \frac{p}{3}, if an aa-element good subset AA is contained in a bb-element good subset BB, i.e., aba \to b, then aa must be a divisor of bb.
*Proof of Conclusion 4:* Without loss of generality, assume good subset B={xk=kpb,k=1,2,,b}B = \{x_k = \lfloor \frac{kp}{b} \rfloor, k = 1, 2, \dots, b\} contains good subset A={yj=xkj,j=1,2,,a}A = \{y_j = x_{k_j}, j = 1, 2, \dots, a\}. If k1,k2,,kak_1, k_2, \dots, k_a are not equally spaced, for example, k2k1>k3k2k_2 - k_1 > k_3 - k_2, then the difference between adjacent elements in AA is
y2y1=xk2xk1(k2k1)pb(k2k11)pb+pb(k3k2)pb+3xk3xk2+2=y3y2+2, 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,
which contradicts the fact that AA is a good subset. Therefore, aa must be a divisor of bb.

Conclusion 5: When p4<a<b<p2\frac{p}{4} < a < b < \frac{p}{2}, except when p3(mod4)p \equiv 3 \pmod 4 with an edge p+14p12\frac{p+1}{4} \to \frac{p-1}{2}, there is no edge between aa and bb.
*Proof of Conclusion 5:* From Conclusion 4, we know at this point p3<b<p2\frac{p}{3} < b < \frac{p}{2}, otherwise b<p3b < \frac{p}{3} and is a multiple of aa, which is impossible. As in the proof of Conclusion 4, assume good subset B={xk=kpb,k=1,2,,b}B = \{x_k = \lfloor \frac{kp}{b} \rfloor, k = 1, 2, \dots, b\} contains good subset A={yj=xkj,j=1,2,,a}A = \{y_j = x_{k_j}, j = 1, 2, \dots, a\}. Let the interval in BB be hk=xk+1xk=kp+pbkpb{2,3}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 AA yj+1yjxk+2xk4y_{j+1} - y_j \ge x_{k+2} - x_k \ge 4, so A=a<p3|A| = a < \frac{p}{3}, i.e., intervals in AA gj=yj+1yj{pa,pa}={3,4}g_j = y_{j+1} - y_j \in \{\lfloor \frac{p}{a} \rfloor, \lceil \frac{p}{a} \rceil\} = \{3, 4\}. Clearly, the sequence h=(h1,h2,,hb)\mathbf{h} = (h_1, h_2, \dots, h_b) is obtained from g=(g1,g2,,ga)\mathbf{g} = (g_1, g_2, \dots, g_a) by replacing each 4 with two consecutive 2s.
If the sequence h\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 h\mathbf{h} there is a segment with t+2t+2 consecutive 2s, another with at most tt 2s between two 3s, with a total difference of at least 2, contradicting BB being a good subset), and all these numbers are even, so they are all equal. This makes the sequence h\mathbf{h} have a smaller period, contradicting the total sum of h\mathbf{h} being the prime number pp. Therefore, h\mathbf{h} contains one 3 and b1b-1 2s, i.e., p=2b+1p = 2b+1. The sequence g\mathbf{g} contains one 3 and a1a-1 4s, i.e., p=4a1p = 4a-1. In this case, take
A={1,5,9,,p2}B={1,3,5,,p2} 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 2u<p<2u+12^u < p < 2^{u+1}, for any chain a1a2aLa_1 \to a_2 \to \dots \to a_L, the sequence a1,a2,a3,a_1, a_2, a_3, \dots before p4\frac{p}{4} multiplies by several times each step, so there are at most u1u-1 numbers (since p4<2u1\frac{p}{4} < 2^{u-1}), thus au>p4a_u > \frac{p}{4}. If au+1<p2a_{u+1} < \frac{p}{2}, then necessarily au=p+14a_u = \frac{p+1}{4}, au+1=p12a_{u+1} = \frac{p-1}{2}, in which case only au=2u1a_u = 2^{u-1} (otherwise au3×2u2>p14a_u \ge 3 \times 2^{u-2} > \frac{p-1}{4}), i.e., p=2u+11p = 2^{u+1}-1.

In summary, Lmax=2×log2(p+1)L_{\max} = 2 \times \lfloor \log_2(p+1) \rfloor. Thus, when 2u<p<2u+112^u < p < 2^{u+1} - 1, L2uL \le 2u, with equality in chain (2). When p=2u+11p = 2^{u+1} - 1, L2(u+1)L \le 2(u+1), with equality in the following chain:
122u12u12u(p2u1)(p2u2)(p2)(p1). 1 \to 2 \to \dots \to 2^{u-1} \to 2^u - 1 \to 2^u \to (p-2^{u-1}) \to (p-2^{u-2}) \to \dots \to (p-2) \to (p-1).

Solution 2

The characterization of good subsets is similar to part (1) in Solution 1. The following discussion simplifies the subsequent proof. Notice that
kpmm{kpm}mmodp. \lfloor \frac{kp}{m} \rfloor \cdot m \equiv \{\frac{kp}{m}\} \cdot m \quad \mod p.
And when k=0,1,,m1k = 0, 1, \dots, m-1, {kpm}\{\frac{kp}{m}\} takes all values from 0,1,,m10, 1, \dots, m-1. Hence, modulo pp, {mkpm}\{m\lfloor \frac{kp}{m} \rfloor\} is equal to {0,1,,(m1)}\{0, -1, \dots, -(m-1)\}. Due to the uniqueness of rotation, any mm-element good subset multiplied by mm (in the sense of modulo pp) consists of consecutive mm numbers. Conversely, if an mm-element subset multiplied by mm consists of consecutive mm numbers, it must be an mm-element good subset.
Let rr be the modular multiplicative inverse of mm modulo pp, then {kpm}{0,r,,(m1)r}modp\{\lfloor \frac{kp}{m} \rfloor\} \equiv \{0, -r, \dots, -(m-1)r\} \mod p. Therefore, any mm-element set is a good subset if and only if it can be written as {a,a+r,,a+(m1)r}modp\{a, a+r, \dots, a+(m-1)r\} \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 mm-element good subset is a pmp-m-element good subset.
*Proof of Conclusion 1:* Based on the above characterization, assume the mm-element good subset is {a,a+r,,a+(m1)r}\{a, a+r, \dots, a+(m-1)r\} (in the sense of modulo pp), then its complement can be written as {ar,a2r,,a(pm)r}\{a-r, a-2r, \dots, a-(p-m)r\} modulo pp. Since the modular multiplicative inverse of pmp-m modulo pp is r-r modulo pp, the set {ar,a2r,,a(pm)r}\{a-r, a-2r, \dots, a-(p-m)r\} is a good subset.

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

Conclusion 3: If km<pkm < p, then any mm-element good subset is contained in some kmkm-element good subset.
*Proof of Conclusion 3:* Assume the mm-element good subset is A={a,a+r,,a+(m1)r}A = \{a, a+r, \dots, a+(m-1)r\} (in the sense of modulo pp). Let ss be the modular multiplicative inverse of kmkm modulo pp, so ksr(modp)ks \equiv r \pmod p. Then AA is contained in the kmkm-element good subset B={a,a+s,,a+(km1)s}B = \{a, a+s, \dots, a+(km-1)s\}.

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

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

*Proof of Conclusion 5:* Multiply all numbers by mm. Then, in the sense of modulo pp, an mm-element good subset becomes a sequence of consecutive mm numbers (since the original common difference was the modular inverse of mm modulo pp), and the nn-element good subset also becomes an arithmetic sequence TT, with a common difference congruent to mn\frac{m}{n} modulo pp, i.e., not congruent to ±1\pm 1 modulo pp. Assume the transformed mm-element good subset is {0,1,,m1}\{0, 1, \dots, m-1\}, with the first term aa of TT in {0,1,,m1}\{0, 1, \dots, m-1\}, and let the common difference be β\beta, where β<p2|\beta| < \frac{p}{2}. Note that p(m1)>p2p - (m-1) > \frac{p}{2}, so every term of TT must be in {0,1,,m1}\{0, 1, \dots, m-1\}, hence m=(m1)+1(n1)β+12n1m = (m-1) + 1 \ge (n-1)|\beta| + 1 \ge 2n-1. When equality holds, β=2|\beta| = 2 must be true, thus mn±2(modp)\frac{m}{n} \equiv \pm 2 \pmod p, meaning 2n1±2n(modp)2n-1 \equiv \pm 2n \pmod p. As nm+12p+14n \le \frac{m+1}{2} \le \frac{p+1}{4}, the only possibility is n=p+14n = \frac{p+1}{4} and m=p12m = \frac{p-1}{2}.

Now returning to the original problem, for any chain of good subsets A1A2ALA_1 \subset A_2 \subset \dots \subset A_L, let Aq<p2|A_q| < \frac{p}{2} and Aq+1>p2|A_{q+1}| > \frac{p}{2}. By Conclusion 5, we have
p+122Aq122Aq22q1A1=2q1. \frac{p+1}{2} \ge 2|A_{q-1}| \ge 2^2|A_{q-2}| \ge \dots \ge 2^{q-1}|A_1| = 2^{q-1}.
Thus, qlog2(p+1)q \le \lfloor \log_2(p+1) \rfloor. By Conclusion 1, the chain of complements ALcAL1cAq+1cA_L^c \subset A_{L-1}^c \subset \dots \subset A_{q+1}^c also forms a chain of good subsets, and similarly, we find Lqlog2(p+1)L-q \le \lfloor \log_2(p+1) \rfloor. Therefore, L2log2(p+1)L \le 2\lfloor \log_2(p+1) \rfloor.

When 2q<p+1<2q+12^q < p+1 < 2^{q+1}, by Conclusions 1, 2, and 3, there exists a chain of good subsets A1A2A2qA_1 \subset A_2 \subset \dots \subset A_{2q}, where Ai=2i1|A_i| = 2^{i-1}, A2q+1i=p2i1|A_{2q+1-i}| = p-2^{i-1}, for i=1,2,,qi=1, 2, \dots, q.

When p=2q1p=2^q-1, by Conclusions 1, 2, 3, and 4, there exists a chain of good subsets A1A2A2qA_1 \subset A_2 \subset \dots \subset A_{2q}, where Ai=2i1|A_i| = 2^{i-1}, A2q+1i=p2i1|A_{2q+1-i}| = p-2^{i-1}, for i=1,2,,q1i=1, 2, \dots, q-1, Aq=2q11|A_q| = 2^{q-1}-1, and Aq+1=2q1|A_{q+1}| = 2^{q-1}.

In summary, the maximum LL sought is 2log2(p+1)2\lfloor \log_2(p+1) \rfloor.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.