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
Problem
Source: China MO 2024, Day 1, Problem 3
Tags: combinatorics
29.11.2023 12:42
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.
29.11.2023 12:56
I think it's very similar to https://artofproblemsolving.com/community/c6h136049p769825 except for the fact it uses a weaker version of Beatty-Rayleigh theorem.
27.09.2024 17:15
This problem is again proposed by 王彬. I spent $\ge 4$ hours on this, but seems only finishing the first page of solution. It is the kind of problem that requires strong analysing skills but not a flash of inspiration.
Attachments:


