$A$ is the set of points of a convex $n$-gon on a plane. The distinct pairwise distances between any $2$ points in $A$ arranged in descending order is $d_1>d_2>...>d_m>0$. Let the number of unordered pairs of points in $A$ such that their distance is $d_i$ be exactly $\mu _i$, for $i=1, 2,..., m$. Prove: For any positive integer $k\leq m$, $\mu _1+\mu _2+...+\mu _k\leq (3k-1)n$.
Problem
Source: 2014 China TST 2 Day 1 Q3
Tags: combinatorics proposed, combinatorics
31.12.2014 08:57
Anybody ideas for this hard problem?
01.11.2015 10:35
This Problem may be solved by Double Counting. I don't know another way..
28.12.2015 08:08
People who took this exam, don't you know the solution?
24.01.2017 19:16
Isn't $ 2kn $ possible too? Well, I think there exist a point $ P $ that there are at most two $ Q $ that $ PQ=d $ for all $ d $. Edited -> Well, this seems like a false one
17.01.2019 09:21
toto1234567890 wrote: Anybody ideas for this hard problem?
05.03.2020 00:52
CEH wrote: toto1234567890 wrote: Anybody ideas for this hard problem? ...
26.03.2021 11:37
It's not surprising that this problem hasn't been solved on AoPS for 7 years, because it is Corollary 2.8 in the following paper: P. Erdős, L. Lovász, K. Vesztergombi: On the graph of large distances, Discrete Comput. Geom. 4 (1989) no. 6, 541--549 ( MR90i:05048; Zentralblatt 694.05031.
17.08.2021 01:36
Let $S$ be the graph created by joining together distances $\ge d_k.$ The crux of the problem is proving that there exists a point $P$ with degree at most $3k-1$ no matter the choice of $n.$ If $n \le 3k$ this is trivial. From then on we assume $n \ge 3k+1$ (this quietly eliminates configuration issues later). Since the polygon is convex, we'll give the points a circular order with respect to a center for notational purposes. Choose $P_2$ to be the nearest point going counterclockwise from $P$ such that $PP_1 \ge d_k.$ Let $P_2$ to be the nearest point going clockwise from $P$ such that $PP_2 \ge d_k$ (if neither point exists we're done already). For two points $A,B,$ let $d(a,b)$ be the number of sides of the convex $n$-gon between $A$ and $B$ going in the counterclockwise direction. WLOG suppose $d(P,P_2)$ is maximized across all possible choices of $P.$ Consider a series of operations on any particular segment $XY \ge d_k.$ We start with the segment $XY.$ Let $X'$ be the counterclockwise neighbor of $X$ and $Y'$ be the clockwise neighbor of $Y.$ We can either move $X$ to $X'$ if $X'Y > XY,$ or move $Y$ to $Y'$ if $XY' > XY,$ yielding a new segment which is either $X'Y$ or $XY'.$ We continue in this way, each step consisting of moving one point at a time on our segment to its clockwise or counterclockwise neighbor. After at most $k-1$ steps on $XY$ (since there are only $k-1$ distances $> d_k,$) we find a segment impossible to make any more steps on, call this the image of $XY.$ Suppose the image of $PP_1$ is $QQ_1,$ where we've moved $P$ and $P_1$ to $Q$ and $Q_1$ respectively. We have $d(P,Q) + d(Q_1,P_1) \le k-1.$ Now choose the point $R$ such that $d(Q, R) = k.$ Let $R_2$ be the nearest point going counterclockwise from $R$ where $RR_2 \ge d_k$ (if this does not exist we're done already). We cannot have $R_2$ lying between $P$ and $P_2$ going counterclockwise due to convexity. Since $d(R,R_2) \le d(P,P_2),$ $d(P_2,R_2) \le d(P,R) = d(P,Q) + k.$ If $R_2$ lies between $Q_1$ and $P$ going counterclockwise we have $$d(P_2,P_1) \le d(P_2,R_2) + d(Q_1,P_1) \le d(P,Q) + k + d(Q_1, P_1) \le 2k-1.$$Otherwise, call the image of $R_2R$ segment $T_2T,$ where $R_2$ and $R$ have moved to $T_2$ and $T$ respectively. We see that $T$ must lie between $Q$ and $R$ going counterclockwise since $d(Q,R) = k \ge k-1.$ Furthermore $TT_2$ and $QQ_1$ must intersect, otherwise either we will be able to continue operations on at least one of the segments, or the polygon isn't convex. So $d(R_2, Q_1) \le d(R_2,T_2) \le k-1.$ We have $$d(P_2,P_1) \le d(P_2,R_2) + d(R_2, Q_1) + d(Q_1,P_1) \le d(P,Q) + k + k-1+ d(Q_1,P_1)\le 3k-2.$$Either way there are at most $3k-1$ vertices between $P_2$ to $P_1$ inclusive going counterclockwise which proves the desired bound. So no matter what $n$ we choose, we may find one point with degree at most $3n-1.$ We may remove this point and all edges joining to it from consideration, at which point we'll still find another point with degree at most $3k-1$ in the remaining subgraph. Then we’l remove this point and all edges joining to it from consideration. Continuing in this way yields the maximum of $(3k-1)n.$ $\square$
10.06.2024 20:48
key point: if it is left to right in the beginning,then once it goes from right to left,it will continue this process until get back to the origin.