Maths Olympiad Prep

Library / /16 of 27

Geometry Difficulty 5.4 AIME, harder Prove it Singapore

Let nn be a positive integer. Determine the minimum number of lines that can be drawn on the plane so that they intersect in exactly nn distinct points.

Solution

Let mm be the integer so that (m2)<n(m+12)\left(\frac{m}{2}\right) < n \le \left(\frac{m+1}{2}\right). Then since mm lines intersect in at most (m2)\left(\frac{m}{2}\right) points, we have n>mn > m. We shall show that there exist m+1m + 1 lines that intersect in exactly nn points. Let p=n(m2)p = n - \left(\frac{m}{2}\right) and q=(mp)/2q = \lfloor (m-p)/2 \rfloor.

Case (i): mpm-p is even. Draw qq pairs of lines so that they intersect in qq distinct points on the xx-axis. Draw another pp lines, not parallel to the xx-axis, so that the 2q+p=m2q+p=m lines are pairwise nonparallel. Then draw another line on the xx-axis. These m+1m+1 lines intersect in exactly nn points.

Case (ii): mpm-p is odd. Draw qq pairs of lines so that they intersect in qq distinct points on the xx-axis. Draw another p+1p+1 lines so that exactly one of them is parallel but not on the xx-axis, and that the 2q+p+1=m2q+p+1=m lines are pairwise nonparallel. Then draw another line on the xx-axis. These m+1m+1 lines intersect in exactly nn points.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.