Here is an outline of the solution. So just note that the number of intersections of segments between these points and some random line is never increasing when we perform the operation. Now we will look at some specific lines and see what happens whit the total number of intersections. More precisely we will look at $2*n (n-1)/2$ lines which are very close to $n (n-1)/2$ possible lines formed by each pair of given points, one above and one below the segment. So now we can easily check that the given operation decresaes the sum number of intersections of all lines and all drawn segments by 4. Now the result easily follows.

aleksam wrote: Here is an outline of the solution. So just note that the number of intersections of segments between these points and some random line is never increasing when we perform the operation. Now we will look at some specific lines and see what happens whit the total number of intersections. More precisely we will look at $2*n (n-1)/2$ lines which are very close to $n (n-1)/2$ possible lines formed by each pair of given points, one above and one below the segment. So now we can easily check that the given operation decresaes the sum number of intersections of all lines and all drawn segments by 4. Now the result easily follows. These points are not in a convex polygon, so the intersections maybe increase in some cases.

This is a nice problem! My solution is as follows: For any segment $AB$ and any point $X$, we define $f(AB,X)$ as follows: If $X=A$ or $X=B$, then $f(AB,X)=0$, otherwise we draw every line passing through $X$ and another point in $M$ so that the round angle is partitioned into $2n-2$ small angles. Let $f(AB,X)$ be the number of small angles inside angle $AXB$ . It is easily to see that $f(AB,X)<n-1$ for all $A,B$ and $X$ . For any situation $K$ , we define $F(K)$ be the sum of all such $f(AB,X)$ , where $AB$ passing through all segments in $K$ and $X$ passing through all points in $M$ . Clearly there are $n$ choices of $AB$ , $n$ choice of $X$ , and $f(AB,X)<n$ for all $A,B$ and $X$, so initially $F$ is less than $n^3$ , and $F$ cannot be negative, so the remaining is to show that after any move, $F$ must be decreased by 4 or more. For any $A,B,C,D,X$ in $M$ , if we changed $AB,CD$ to $AC,BD$ , we know quadrilateral $ACBD$ is convex. We consider $f(AB,X)+f(CD,X)-f(AC,X)-f(BD,X)$ . Case 1: $X$ belongs to one of $A,B,C,D$ . WLOG let $X=A$ , then $ACBD$ is a convex quadrilateral, so angle $BAD$ lies in the interior of angle CAD, which follows that $f(AB,X)+f(CD,X)-f(AC,X)-f(BD,X)=f(CD,A)-f(BD,A)=f(BC,A) \ge\ 1$ ; Case 2: $X$ lies outside the quadrilateral $ACBD$. Draw a line $l$ passing through $X$ and donot intersect quadrilateral $ACBD$ and rotate it clockwise from point $X$ .WLOG let $A$ be the first point be touched by $l$ in the rotation, then $B$ cannot be the second otherwise $AB$ and $CD$ cannot intersect. If $C$ is the second, then $f(AB,X)+f(CD,X)>f(AC,X)+f(BD,X)$, if $D$ is the second, then $f(AB,X)+f(CD,X)=f(AC,X)+f(BD,X)$. (It is clear by drawing the figure) Case 3: $X$ lies inside the quadrilateral $ACBD$. Let $O$ be the intersection of $AB,CD$, we consider which triangle contains $X$. By symmetry, we only consider two cases, that is, $X$ is in triangle $AOC$, and $X$ is in triangle $COB$. If $X$ is in triangle $AOC$, then $f(AB,X)+f(CD,X)-f (AC,X)-f(BD,X)=2n-2-2f(AC,X)>0$; If $X$ is in triangle $COB$, then $f(AB,X)+f(CD,X)-f(AC,X)-f(BD,X)=2f(AD,X)>0$. So, $f(AB,X)+f(CD,X)-f(AC,X)-f(BD,X)$ will decrease at least 1 where $X$ belongs to one of $A,B,C,D$, and will not increase where $X$ does not belong to one of $A,B,C,D$. For this reason, $F$ must be decreased by 4 or more after any move, which follows the conclusion.

Yunhao Fu wrote: These points are not in a convex polygon, so the intersections maybe increase in some cases. It is not saying about # of intersection of segments, but talking about # of intersection between "Line and Segment". For instance, try this example below.

Attachments:

Isogonics wrote: Yunhao Fu wrote: These points are not in a convex polygon, so the intersections maybe increase in some cases. It is not saying about # of intersection of segments, but talking about # of intersection between "Line and Segment". For instance, try this example below. Yeah, I got it. It seems to be the same function as which I built, but much easier to explain.

Can someone please tell the motivation behind double counting that particular thing. Like, I agree one might think of number of intersections in some way ; but how to think looking at the all red lines at once and double counting the exact precise thing ?

This doesn't seem similar to any of the above solutions nor the official sol, but I believe it does work (although there is a good chance it does not). Also my 777th post! I will show the result for $n$ lines and $m$ points. Ignore the fact that every point in $M$ is the endpoint of $2$ segments. Pick $2$ points $A,B \in M$. Claim: A move involving $AB$ can occur at most $n-1$ times Proof: We divide all lines present into $4$ types: a) If a line is between points $A,B$, it is called a good line. b) If a line has exactly one endpoint as one of $A,B$, it is called a potential line. c) If a line has both its endpoints on opposite sides of the line $AB$ (In different halfplanes), it is called a cutter line. d) If a line has both its endpoints on only one side of line $AB$ (In the same halfplane), it is called a harmless line. Now, we consider what happens when we perform a move: 1. If a move involves a cutter and a good line, then it forms two potential lines. 2. If a move involves two potential lines, then it forms a good line and a harmless line. Its easy to check that any other move leaves the types of the lines unchanged. Note that each time $AB$ is operated on, it uses a cutter line. But no other time is a cutter line ever created, so they must have been present to start with. Since there are only $n-1$ other lines, there can only have been $n-1$ cutter lines at the beginning so $AB$ can only have been operated on, at most $n-1$ times, as claimed. $\square$ Now, suppose $N$ moves have been made overall. Since every move operates on $2$ lines(pairs of points) and there are $\binom{m}{2}$ pairs of points, each of which are operated on at most $n-1$ times, we have the bound $2N \le (n-1)\binom{m}{2} = \frac{m(m-1)(n-1)}{2}$, which gives $\boxed{N \le \frac{m(m-1)(n-1)}{4}}$. The problem now follows since $m = n \implies N \le \frac{n(n-1)^2}{4} < \frac{n^3}{4}$, as desired. $\blacksquare$

At this point I've asked Evan for so many hints that I can say "solved with Evan Chen" Note that $\overline{XY}$ refers to a segment, not a line, unless otherwise specified In fact we can get the bound of $\frac{m(n-2)(n-3)}{4}$ if we have $n$ points and $m$ segments (interestingly, @above gets a rather different bound! EDIT: wait nvm they just used different variable names lol). Consider the number of pairs $(s,\ell)$ where $s$ is a segment that's present and $\ell$ is a line connecting (any) two points in $M$, such that $\ell$ and $s$ intersect in the interior of $s$; call this quantity $N$. Clearly there are $m$ ways to pick $s$, and then at most $\binom{n-2}{2}$ ways to pick $\ell$, since we can't use either endpoint of $s$, hence $N \leq \frac{m(n-2)(n-3)}{2}$. Suppose that we perform an operation $\overline{AB}, \overline{CD} \to \overline{AC}, \overline{BD}$, and define $X=\overline{AB} \cap \overline{CD}$. Check that this does the following: Any $\ell$ will intersect at least as many segments as it did prior to the operation: if $\overline{AC}$ intersects $\ell$, then $\ell$ must "exit" $\triangle AXC$, in the process intersecting either $\overline{AB}$ or $\overline{CD}$. The same goes for $\overline{BD}$. The pairs $(\overline{AB}, \overline{CD})$ and $(\overline{CD}, \overline{AB})$, where first elements are segments and second elements are lines, are removed. Clearly they used to intersect and now they don't, hence lines $\overline{AB}$ and $\overline{CD}$ "lose" a segment intersection. Combining these two facts implies that each operation decreases $N$ by at least $2$, hence we can make at most $\frac{N}{2}\leq \frac{m(n-2)(n-3)}{4}$ moves. Obviously, this implies the original problem by taking $m=n$. $\blacksquare$

guptaamitu1 wrote: Can someone please tell the motivation behind double counting that particular thing. Like, I agree one might think of number of intersections in some way ; but how to think looking at the all red lines at once and double counting the exact precise thing ? I didn't solve the problem on my own so I might not be the best person to answer this question, but I think a somewhat realistic pathway is as follows: First, note that the process terminates in a finite number of moves because every move decreases the sum of segment lengths, which suggests that some similar monovariant-type solution for this problem. Now, also remember that the proof for every move decreasing the sum of segment lengths is by drawing all four segments (before and after), and then partitioning the resulting figure into triangles to use the triangle inequality. This might lead us to do the same here: what can be said about these triangles? One might also wonder where $n^3/4$ comes from (really, the important part about it is that it's $O(n^3)$). Because we were previously summing some property over segments (length), we probably want to do the same here as well. Also, summing over points, which is the other option that immediately jumps to mind, probably won't lead anywhere because the "degree" of each point remains the same (it's hard to obtain anything from that perspective). We would also like the quantity of whatever we're counting to be $O(n^2)$ per segment. Here we might experiment a little: what if, for every point, we ranked the distances from all the other points (from low -> high), and defined the weight of a segment to be the sum of the ranks of each endpoint, viewed from the other endpoint? Well that would give us $O(n)$ per segment which is too low. Among our $O(n^2)$ options, something like summing the squares seems overly convoluted, and the product straight up doesn't work. What if we took a step back and considered pairs of segments in some way? There are $O(n^2)$ of those, so our quantity would have to be $O(n)$. But nothing seems to even possibly fit that, since points wouldn't work as mentioned before, segment rank sums are equivalent to the previous case but multiplied by $n$, and it doesn't feel like anything else exists. At this point one might take another leap of faith and realize that there are $O(n^2)$ pairs of points, so if we count something related to pairs of points and segments, we might get out answer. Pairs of points naturally correspond to lines (line segments, including ones that aren't present, doesn't seem to work, and I'm sure you can try them and get stuck or motivate thinking about lines instead). We're almost there. Remember the two triangles. What's true about a line and a triangle? If they intersect once, they intersect twice (minus edge cases that don't matter). And from that we get the quantity we wish to count. Hopefully this makes sense.

What kind of problem is this??? My solution literally stems from the infinite monkey theorem... First let's note things in the diagram with a low degree count. There are on the order of $n$ of the following: 1. Segments, 2. Lines, 3. Points There are on the order of $n^2$ of the following: 1. Possible segments, 2. Possible lines, 3. Possible neighbor sets of a given vertex There are on the order of $n^3$ of the following: 1. Possible cherries There are on the order of $n^4$ of the following: 1. Sets of ABCD Now mix and match until you get a product on the order of $n^3$. AFTER A WHILE (that's an understatement), finally we stumble upon the combination of "Segments" and "Possible lines". You now notice that any line's number of intersections with segments is weakly decreasing, and simply choosing a nice selection of lines, basically taking the original ${n \choose 2}$ and shifting each one infinitesimally away from its original position in two ways, gives a total of ${n \choose 2} \cdot 2 \cdot n$ incidences. Each move, this decreases by at least four by analyzing the lines through the relevant points, so we are done since $\frac{{n \choose 2}\cdot 2 \cdot n}{4} \leq \frac{n^3}{4}$ Great problem, LOVE the motivation. (Still have no clue how to properly motivate this other than RNG)

@above what are cherries and neighbor sets? (absolutely agree with the claim that there's zero motivation for the solution other than trying to match stuff together until something clicks)

IAmTheHazard wrote: @above what are cherries and neighbor sets? Just random ideas I had that didn't work out. Cherries are triples of vertices u, v, w such that uv and uw are edges. They work well with $C_4$ of edges (AB, CD, AC, BD) since a $C_4$ has $4$ directed cheries and there are $n^3$ directed cheries total, so you're guaranteed to have two operations that both had the same effect on some cherry subgraph. This gives $\frac{n^3}{4}$ but it doesn't lead anywhere. Neighbor sets are just the pair of vertices a given vertex is connected to, possibly ordered. I was thinking if you could show the same set of neighbors can't occur more than once under most circumstances you would be good since there would be $n^3$ distinct ordered neighbor sets over all vertices and each operation changes the neighbor sets of the four involved vertices, giving the $\frac{n^3}{4}$ but the idea doesn't lead anywhere either.

Define $\mathcal L=\left \{ \overline{XY} \mid X,Y\in M \right \}$, let $\mathcal S$ be a set of presented segments. For every $a\in \mathcal S$ define $\mathcal L_{a}\subset \mathcal L$ as a set of all lines intersecting $a$ at the interior. We will track the sum $\sum_{a\in \mathcal S} |\mathcal L_a|;$ consider two intersecting segments $AB,CD.$ Claim 1. $|\mathcal L_{AC} \cup \mathcal L_{BD}|\leq |\mathcal L_{AB} \cup \mathcal L_{CD}|-2.$ Proof. Firstly $\overline{AB} \cup \overline{CD}\in (\mathcal L_{AB} \cup \mathcal L_{CD})\backslash (\mathcal L_{AC} \cup \mathcal L_{BD}).$ Next, any line $\ell \in \mathcal L_{AC} \cup \mathcal L_{BD} \backslash \left \{ \overline{AC},\overline{BD} \right \}$ intersect at least one of segments $AB,CD$, i.e. $\ell \in \mathcal L_{AB} \cup \mathcal L_{CD}$. The conclusion follows from injection $\Box$ Claim 2. $|\mathcal L_{AC} \cap \mathcal L_{BD}|\leq |\mathcal L_{AB} \cap \mathcal L_{CD}|.$ Proof. Clearly $\ell \in \mathcal L_{AC} \cap \mathcal L_{BD}$ intersect both diagonals of convex quadrilateral $ACBD,$ hence the conclusion $\Box$ Summing up we obtain that replacing of segments decreases the tracking sum by at least $2.$ It's suffice to note that $$\forall s\in \mathcal S:|\mathcal L_{s}|\leq \binom n2<\frac{n^2}{2}\implies |\mathcal L|<\frac{n^3}{2}.$$

IAmTheHazard wrote: absolutely agree with the claim that there's zero motivation for the solution other than trying to match stuff together until something clicks The first thing I thought was that maybe the number of intersections decreases(after all the process is literally getting rid of intersections greedily). That's false, but notice that for a new intersection to form, it must have an endpoint inside the quadrilateral, which is weird, it still intersects the quadrilateral. Since the diagonals span the quadrilateral we shift our attention to lines which by previous analysis never give new intersections. I found it difficult to determine what lines exactly one should consider since my thinking lead me to focus only on the lines determined by our points, which gives the bound of $\frac{n^3}2$.

I didn't really solve this problem, but I thought of the 30% OTIS hint (to consider a discrete version of the sum of Euclidean distances monovariant) before I looked at ARCH and solved the problem from there after confirmation that the 30% hint was useful, and I was motivated by the following: Consider the case where the points form a convex polygon. In that case, each move decreases the number of intersections between pairs of segments. However, this doesn't generalize to all configurations. But if you look at the convex polygon case, you can define a discrete version of distance where points adjacent on the polygon have distance $1$, points sharing a neighbor have distance $2$, and so on. This intuitive definition of distance was nice but impossible to generalize. However, you could generalize a slightly less intuitive version of distance or length: a segment $\ell$ has length equal to the number of segments through two points passing through $\ell$. In convex polygons, this gives a distance of $(k-1)(n-k-1)$ between points that are $k$ edges apart. This seemed promising, so I tried to generalize it for all configurations. However, I ran into the following problem: if $ABCD$ is a quadrilateral, $\overline{AC}$ and $\overline{BD}$ intersects at $E$, and there exists a point $P$ inside $\triangle AEB$ and many points on the opposite side of $\overline{AB}$ as $P$ and between rays $PA$ and $PB$, then switching $\overline{AC}$ and $\overline{BD}$ with $\overline{AB}$ and $\overline{CD}$ increases the sum of the "lengths" of the segments. This is because the segments through $P$ and the points on the other side of $\overline{AB}$ makes $\overline{AB}$ have relatively large length. However, this large length is not necessarily also distributed on $\overline{AC}$ and $\overline{BD}$ because our definition of the length of $\ell$ only looks at segments through $\ell$. Thus, I changed it to number of lines through $\ell$, and it worked.

I have read the official solution to this problem. In this post I tried to motivate why we should choose that particular monovariant.

I can prove that the number of moves is less than or equal to $\frac{n^2(n-1)}8$. The main idea is to project onto a straight line, then calculate the number of projection line segments with common parts on each class of projection, and finally classify the projection sequence appropriately

Let $\overline{AB}$ denote the segment between $A$ and $B$, let $AB$ denote the line between $A$ and $B$. Denote $s(A,B)$ denote the number of unordered pairs of points $C,D\neq A,B$ such that $\overline{AB}$ intersects $CD$. Suppose $A$, $B$, $C$, $D$ were four points in general position such that $\overline{AB}$ intersects $\overline{CD}$ at $E$. If a line $\ell$ passes through $\overline{AD}$ then it passes through either $\overline{AE}$ or $\overline{DE}$. If it passes through $\overline{BC}$ then it passes through $\overline{BE}$ and $\overline{DE}$. Therefore for all $\ell$, if $\ell$ passes through either $\overline{AD}$ or $\overline{BC}$ then it passes through either $\overline{AC}$ or $\overline{BD}$. If $\ell$ passes through both $\overline{AD}$ and $\overline{BC}$ and it doesn't pass through both $\overline{AB}$ and $\overline{CD}$ then it passes through both $\overline{DE}$ and $\overline{CE}$ or it passes through both $\overline{AE}$ and $\overline{BE}$. It both cases, it passes through $E$ which means it passes through both segments anyway. However note that $\overline{AB}$ intersects $CD$ and $\overline{CD}$ intersects $AB$ while $\overline{AD}$ cannot intersect $BC$ and $\overline{BC}$ cannot intersect $AD$ because $ABCD$ is necessarily convex. Therefore, $s(A,D)+s(B,C)\le s(A,B)+s(C,D)-2$. Every move, the value \[\sum_{A,B\text{ are connected}}{s(A,B)}\]decreases by at least two. The starting value is at most $n\tbinom{n-2}{2}$ so the total number of times you can move less than $n^3/4$.