Maths Olympiad Prep

Library / /22 of 27

Combinatorics Difficulty 6.1 National Olympiad Prove it Singapore

Determine the minimum number of lines that can be drawn on the plane so that they intersect in exactly 200200 distinct points.
(Note that for 33 distinct points, the minimum number of lines is 33 and for 44 distinct points, the minimum is 44.)

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.