AoPS - Problem

Source: China MO 2024, Day 1, Problem 3

Tags: combinatorics

Photaesthesia

28.11.2023 09:07

Let $p \geqslant 5$ be a prime and $S = \left\{ 1, 2, \ldots, p \right\}$. Define $r(x,y)$ as follows: \[ r(x,y) = \begin{cases} y - x & y \geqslant x \\ y - x + p & y < x \end{cases}.\]For a nonempty proper subset $A$ of $S$, let $$f(A) = \sum_{x \in A} \sum_{y \in A} \left( r(x,y) \right)^2.$$A good subset of $S$ is a nonempty proper subset $A$ satisfying that for all subsets $B \subseteq S$ of the same size as $A$, $f(B) \geqslant f(A)$. Find the largest integer $L$ such that there exists distinct good subsets $A_1 \subseteq A_2 \subseteq \ldots \subseteq A_L$. Proposed by Bin Wang

The answer probably is 2[log(p+1)/log(2)]. But still many cases to consider. Notice if |A|=k is a good set, then its points should be equidistributed on a circle, they should be something like [ip/k], i=0,...,k-1. The reason is that this set minimize each part with the square of (sum of s segments). Also if a set is good then its complement should also be good by definition (and some calculation). Also a good set A is contained in a rotation of its complement if |A|< p/2. Then there are many cases to consider if one contains another (I hope there is a simple way to do it) . This leads to 2[log(p+1)/log(2)] numers of good sets.