Let $m$ and $n$ be positive integers. A sequence of points $(A_0,A_1,\ldots,A_n)$ on the Cartesian plane is called interesting if $A_i$ are all lattice points, the slopes of $OA_0,OA_1,\cdots,OA_n$ are strictly increasing ($O$ is the origin) and the area of triangle $OA_iA_{i+1}$ is equal to $\frac{1}{2}$ for $i=0,1,\ldots,n-1$. Let $(B_0,B_1,\cdots,B_n)$ be a sequence of points. We may insert a point $B$ between $B_i$ and $B_{i+1}$ if $\overrightarrow{OB}=\overrightarrow{OB_i}+\overrightarrow{OB_{i+1}}$, and the resulting sequence $(B_0,B_1,\ldots,B_i,B,B_{i+1},\ldots,B_n)$ is called an extension of the original sequence. Given two interesting sequences $(C_0,C_1,\ldots,C_n)$ and $(D_0,D_1,\ldots,D_m)$, prove that if $C_0=D_0$ and $C_n=D_m$, then we may perform finitely many extensions on each sequence until the resulting two sequences become identical.
Problem
Source: China TST 2011 - Quiz 3 - D2 - P3
Tags: analytic geometry, graphing lines, slope, geometry, parallelogram, combinatorics unsolved, combinatorics
28.05.2011 10:37
20.03.2017 18:54
We consider two exciting sequence $A=(X,A_1,A_2,...,A_n,Y)$ and $B=(X,B_1,B_2,...,B_m,Y)$. With all exciting sequence $K$, call $t(K)$ is the angle between $OU$ and $OV$($U$, $V$ is end point and first point of $K$) There is a rectangle $H$ which consists all these $m+n+2$ points and $O$ , call the set of all lattice points inside that rectangle $T$. We define $M=\left \{ \measuredangle AOB \mid A,B\in T \right \}$, $m$ is the minimal element in $M$ that is greater than $0$. $S_{OXA_1}=S_{OXB_1} \Rightarrow A_1B_1 \parallel OX$. We assume that $OA_1$ is between $OX$ and $OB_1$, call the lattice points lie on the segment $A_1B_1$ are $A_1=C_0,C_1,C_2,...,C_t=B_1$ in that order. By Pick's theorem, $C_iC_{i+1}=OX$ with all $i=\overline{0;t-1}$. We extend $(X;C_i)$, there'll be the point $C_{i-1}$. Then, we can perfom extensions to turn $B$ into $(X;A_1;C_1;C_2;...;B_1:A_2;...;A_n;Y)$. Remove point $X$ from both sequence, we have two interesting sequence $A',B'$ with the same end point and first point. We can easily see that $C_i \in T$ with all $i$ and $t(A')=\measuredangle A_1OY\leq \measuredangle XOY-m=t(A)-m$. That index is always non-negative, so we have to stop adding and removing points.Then add all the points we removed, we have to same exciting sequence which is a extensions of both $A$ and $B$ $(Q.E.D)$
12.04.2020 12:43
09.05.2020 03:40
bumjoooon wrote:
However ,you added many points in step 1 to ensure the sequences have more points in common. Then the points you added became new"troubles" so you can't make sure the algorithm will end. At least I can not see your method to fix this in your solution
10.05.2020 06:41
@xdfzchen No, it’s not the problem. It’s true that new points are created while iterating the algorithm. However, the point created is still in the convex hull of original $O, A, B$. Also, since new point can be created at most twice(on the side of $A$ and $B$ each) the iteration step cannot create infinitely many points.
27.09.2021 18:59
An interesting sequence will remain interesting after extension. Let $B_i = (a,b)$ and $B_{i+1} = (c,d).$ The slope of $B = (a+c,b+d)$ wrt to the origin is between that of the slopes of $B_i$ and $B_{i+1}$ to the origin. Furthermore, $|a(b+d) - b(a+c)| = |(a+c)d - (b+d)c| = |ad-bc| = 1.$ Second, if the starting points $P, Q$ of some sequence are in different quadrants, then at some point two adjacent points must lie in different quadrants (or one of them lies on the axis between adjacent quadrants). We can see that one of these points must be either $(0,1); (0,-1); (1,0);$ or $(-1,0)$ to ensure that the triangle has area $1/2,$ and the former two aren't achievable since they have undefined slopes with $O.$ The points go from quadrant $4$ to quadrant $1,$ or the points go from quadrant $3$ to quadrant $2$. Either way, any two sequences going from $P$ to $Q$ must have a subsequence in one common quadrant followed a common point of $(-1,0)$ or $(1,0),$ followed by a subsequence in a second shared quadrant (sequences passing through three quadrants are not possible). We may deal with these subsequences independently of each other and thus relegate our problem to sequences in one quadrant. Suppose WLOG this is the first quadrant. Take two arbitrary sequences that are counterexamples. Take the convex hull of these two sequences, and take the two sequences of greatest total size $(C_0,C_1,\ldots,C_n)$ and $(D_0,D_1,\ldots,D_m)$ that lie completely within this convex hull and are also counterexamples. Take the first index $i \ne 0$ where $C_i \ne D_i,$ WLOG this is $1.$ Let $C_0 = D_0 = (a,b),$ $C_1 = (c_1,c_2)$ and $D_1 = (d_1,d_2).$ Suppose WLOG $c_1+c_2 \le d_1+d_2.$ We have $ac_2 - bc_1 = 1$ and $ad_2 - bd_1 = 1.$ But also $a,b$ are relatively prime so $d_2 = kb +c_2$ and $d_1 = ka+c_1$ for some positive integer $k.$ We insert $(a+kc_1, b+kc_2) = (d_1,d_2); \cdots (2a+c_1, 2b+c_2); (a + c_1, b+c_2)$ between $(a,b)$ and $(c_1, c_2)$ in that order. We've increased the size of these two sequences without increasing the convex hull. If these two new sequences are not counterexamples, then the two sequences we started with weren't counterexamples either. $\square$
19.06.2024 15:07
Seems that it has something to do with Farey sequences.Are there any solution? (p.s. This question is from SLW)