Anybody ideas for this hard problem?

This Problem may be solved by Double Counting. I don't know another way..

People who took this exam, don't you know the solution?

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

toto1234567890 wrote: Anybody ideas for this hard problem?

CEH wrote: toto1234567890 wrote: Anybody ideas for this hard problem? ...

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.

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$

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.