Given a set $ \mathcal{H}$ of points in the plane, $ P$ is called an "intersection point of $ \mathcal{H}$" if distinct points $ A,B,C,D$ exist in $ \mathcal{H}$ such that lines $ AB$ and $ CD$ are distinct and intersect in $ P$. Given a finite set $ \mathcal{A}_{0}$ of points in the plane, a sequence of sets is defined as follows: for any $ j\geq0$, $ \mathcal{A}_{j+1}$ is the union of $ \mathcal{A}_{j}$ and the intersection points of $ \mathcal{A}_{j}$. Prove that, if the union of all the sets in the sequence is finite, then $ \mathcal{A}_{i}=\mathcal{A}_{1}$ for any $ i\geq1$.
Problem
Source: Iberoamerican 2004 problem 6
Tags: induction, quadratics, function, geometry, parallelogram, combinatorics proposed, combinatorics
hjbrasch
18.09.2007 17:31
Induction on the number of prime divisors of $ n$ (not elegant, but it works). As for the induction start assume $ n=p^{t}$. If $ p=2$ holds, set $ a=1,b=k-1$ and remember that $ k$ must be even then. If $ p>2$ choose any residue $ a$ different from $ 0,k\bmod{p}$ and set $ b=k-a$. As for the induction step write $ n=p^{t}n'$ with $ p$ an odd prime and $ n'$ not divisble by $ p$. Since $ n,n'$ have the same parity, we can assume the existence of integers $ a'+b'=k$, which are both coprime to $ n'$. Consider the quadratic function $ x\rightarrow f(x)=(a'+xn')(b'-xn')$, which is not identical to zero modulo $ p$, since $ n'^{2}$ is not divisible by $ p$. Therefore, there exists $ x$ such that $ f(x)$ is not divisible by $ p$ and we can set $ a=a'+xn', b=b'-xn'$ to complete the proof.
freemind
28.09.2007 22:40
Suppose $ \cup_{j=0}^{\infty}$ is finite. Then for some $ j$, $ A_j=A_{j+1}=\ldots$ and $ A_j$ is finite. Suppose in $ A_j$ we have $ 4$ points such that one of them is strictly inside the nondegenerate triangle formed by the other $ 3$. Among all such quadruples of points (in finite number, because $ A_j$ is finite), take $ 4$ such that the area of the triangle containing the $ 4$th point is minimal. Say these points are $ P\in\textrm{Int}(ABC)$. Then $ A'=AP\cap BC$, $ B'=BP\cap CA$ and $ C'=CP\cap AB$ are all in $ A_{j+1}$ and hence, by the choice of $ j$, in $ A_j$. It is easy to see that $ P\in\textrm{Int}(A'B'C')$ and $ [A'B'C']<[ABC]$. Then the choice of $ P,A,B,C$ is contradicted. Thus no such points exist. Assume there are $ 4$ points $ A,B,C,D$ in $ A_j$ such that $ ABCD$ is a non-degenerate 'normal' convex quadrilateral. Let $ P=AC\cap BD$. Then $ P\in A_{j+1}$ and hence $ P\in A_j$. Assume $ ABCD$ is not a parallelogram. Assume $ AB$ isn't parallel to $ CD$. Then $ Q=AB\cap CD$ is in $ A_j$ and from the convexity of $ ABCD$, we have $ P\in\textrm{Int}(QAB)$ or $ P\in\textrm{Int}(QCD)$. Contradiction. Thus any $ 4$ points of $ A_j$, no $ 3$ of them collinear, form a parallelogram. Assume now there is a parallelogram in $ A_j$. Let it be $ ABCD$ and let $ P=AC\cap BD$. Suppose there exists some other point $ Q$ in$ A_j$. IF $ Q\notin AC$ and $ Q\notin BD$ then $ QP$ intersects some side of $ ABCD$, say $ AB$, in its interior - at $ R$. It follows $ R\in A_j$. But then $ P\in\textrm{Int}(RCD)$, impossible. Let now $ Q\in AC$, $ QA>QC$. Then $ QBDC$ isn't a parallelogram. Contradiction. Thus no such $ Q$ exists. Then $ A_j$ is either the set $ \{A,B,C,D,P\}$ with $ ABCD$ parallelogram and $ P=AC\cap BD$, or no parallelogram and no quadrilateral in $ A_j$ exists. This means that $ A_j$ is a set of several collinear points or a set of collinear points plus one more point not collinear with the rest. In any of the possibilities for $ A_j$ it is quite clear that no subset of it can generate it as described in the statement of the problem. This means $ A_{j-1}=A_j$, or $ A_0=A_1=\ldots$, as desired. Hope it's correct...