There's a convex $3n$-polygon on the plane with a robot on each of it's vertices. Each robot fires a laser beam toward another robot. On each of your move,you select a robot to rotate counter clockwise until it's laser point a new robot. Three robots $A$, $B$ and $C$ form a triangle if $A$'s laser points at $B$, $B$'s laser points at $C$, and $C$'s laser points at $A$. Find the minimum number of moves that can guarantee $n$ triangles on the plane.
Problem
Source: Taiwan TST 2016 Round 3
Tags: combinatorics
10.07.2016 07:58
I guess that $\frac{9n^2-7n}{2}$ is the required answer, since I found some arrangements requiring $\frac{9n^2-7n}{2}$ moves for some small $n$. Does any one have any idea?
10.07.2016 08:00
You can try the $2n$ case by replacing triangle with two robot pointing to each other.
12.12.2016 16:40
it's so hard~~~~~
20.02.2017 16:02
At least, we can guarantee that $ \frac{9n^2-3n}{2} $ is possible.
19.04.2017 04:51
11.01.2022 03:16
We first solve the problem if $3n$ were replaced by $2n$ and we want 2-cycles. The answer is $2n(n-1)$ dollars. Construction: $1\rightarrow 2\rightarrow \cdots \rightarrow 2n\rightarrow 1$ To get $a\rightarrow b\rightarrow a$ (where $a<b$), I need $(b-a-1)+(2n+a-b-1)=2n-2$ moves. Since we have $n$ cycles, we need at least $2n(n-1)$ moves. Proof of optimality: we claim that if we pick a random pairing $a_i\rightarrow b_i\rightarrow a_i$, then we expect $2n(n-1)$ moves from any given starting configuration. Note each vertex is equally likely to point to any other vertex that isn't itself. Therefore, it has equal probability of needing to move $0,1,\cdots,2n-2$ times, so it is expected to move $n-1$ times. Now we solve the actual problem. The above ideas are somewhat helpful. The answer is $\frac{9n^2-7n}{2}$. Let $f(k)$ be the number (of the robot) robot k points to. Construction: $f(1)=2, f(2)=\cdots=f(3n)=1$. If $1<x<y<z\le 3n$ then we need $x+y+z-5$ moves. If $1\rightarrow a\rightarrow b\rightarrow 1$, we need $(a-2)$ moves to change $f(1)$ and (at least) $b-2$ moves to change $f(a)$. Summing, we have $\sum\limits_{j=2}^{3n} j - 5(n-1)-4=\frac{(3n+1)3n}{2}-5n=\frac{9n^2-7n}{2}$. It remains to show it is optimal. The above probabilistic method guarantees $\frac{9n^2-6n}{2}$ by noting each vertex is expected to change $\frac{3n-2}{2}$ times, which is $\frac n2$ more than what we want. We can do better by deciding whether to use $a\rightarrow b\rightarrow c\rightarrow a$ or $a\rightarrow c\rightarrow b\rightarrow a$. If their lengths differ by at least 1 for each cycle, I am done. We can use casework to see this is always true: there are three intervals, $[a,b], [b,c], [c,a]$. Case 1: $f(a),f(b),f(c)$ in the same interval. In this case, if I think of the $3n$ numbers on a circle, I can see that $a\rightarrow b\rightarrow c\rightarrow a$ save x steps, where x is the number of {a,b,c} such that f(t) goes through t, or $a\rightarrow c\rightarrow b\rightarrow a$, which saves 3-x steps. Case 2: All in different intervals: verification is clear because one way travels strictly more than the other for all three pointers Case 3: Two in the same interval Therefore, each cycle can be optimized by at least $\frac 12$. The end.
13.02.2022 16:03
We claim that the minimum number of moves is $\frac{9n^2-7n}2$. We will first show that it needs at most $\frac{9n^2-7n}2$ moves. Consider a triangle chosen from the $3n$ vertices uniformly at random. Then, it takes an expected value of $\frac{3n-2}2\cdot3$ moves to rotate every vertex of the triangle such that each robot points to the next robot in the triangle. If $a$ is the minimum number of moves such that the robots in the triangle are pointing to each other in counterclockwise order and $b$ is the minimum number of moves such that the robots in the triangle are pointing to each other in clockwise order. Then, we must have $b\equiv a+3n\pmod{3n-1}$, so $|b-a|\geq1$. Therefore, $\min(a,b)\leq\frac{a+b}2-\frac12$, which means that the expected number of moves is at most $\frac{9n-7}2$, so it is possible to perform at most $\frac{9n^2-7n}2$ moves to form $n$ disjoint triangles.\newline \newline Now, we will show that there exists a construction that requires at least $\frac{9n^2-7n}2$ moves. Suppose that the vertices are labeled $1$, $2$, $\ldots$, $3n$ in counterclockwise order. Suppose that $a_i$ is the robot that the robot on vertex $i$ faces. Then, let $a_1=2$ and $a_2=a_3=\ldots=a_{3n}=1$. Suppose that $b_i$ is the number of robots between $i$ and $a_i$ in counterclockwise order, including $a_i$ but not including $i$. If there are $n$ disjoint triangles, then we must have $b_1+b_2+\ldots+b_{3n}=3n^2$. Since at the beginning, we have $b_1=1$ and $b_i=3n+1-i$ for $i\neq1$. Then, in each move, either $b_i$ increases by $1$ or decreases by $3n-2$. If $b_i$ decreases by $3n-2$ twice in a sequence of moves, then $b_i$ must have been moved at least $3n-1$ times, so by removing $3n-1$ of those moves, it is possible to decrease the number of moves. In each move, if $b_i$ increases by $1$, then $a_i$ increases by $1$ mod $3n$, and if $b_i$ decreases by $3n-2$, then $a_i$ increases by $2$ mod $3n$. If there are $n$ triangles, then all of the $a_i$ must be distinct, so the sum of all of the $a_i$ must be $\frac{3n(3n+1)}2$. Therefore, if there are $x$ moves that increase $b_i$ by $1$ and $y$ moves that decrease $b_i$ by $3n-2$, we have \begin{align*} x-y(3n-2)&=3n^2-1-\frac{(3n-1)3n}2\\&=-\frac32n^2+\frac32n-1\\ x+2y&\geq\frac{3n(3n+1)}2-3n-1\\&=\frac92n^2-\frac32n-1. \end{align*} Therefore, subtracting the first equation from both sides of the second inequality, we have $$3ny\geq6n^2-3n,$$which means that $y\geq2n-1$, which means that $$x=-\frac32n^2+\frac32n-1+y(3n-2)\geq-\frac32n^2+\frac32n-1+(2n-1)(3n-2)=\frac92n^2-\frac{11}2n+1.$$Therefore, this means that $x+y\geq\frac92n^2-\frac{11}2n+1+2n-1=\frac{9n^2-7n}2$, so the minimum number of moves is at least $\frac{9n^2-7n}2$. Therefore, the minimum number of moves that can guarantee $n$ triangles is $\boxed{\frac{9n^2-7n}2}$.