Join each of m points on the positive x-axis to each of n points on the positive y-axis. Assume that no three of the resulting segments are concurrent (except at an endpoint). How many points of intersection are there (excluding endpoints)?
Solution
Answer: mn(m-1)(n-1)/4.
Let us call the points on the y-axis y1 < y2 < ... < yn and the points on the x-axis x1 < x2 < ... < xm. Let us join first y1 to each xi, then y2 and so on. Joining y1 to each of the xi creates no intersections. Joining y2 to x1 creates m-1 intersections. Joining it to x2 creates m-2 intersections and so on. So, in all, joining y2 gives 1 + 2 + ... + m-1 = m(m-1)/2 intersections.
Similarly joining y3 to x1 gives 2(m-1) intersections. Joining it to x2 gives 2(m-2) and so on. So, in all, y3 gives 2 x m(m-1)/2. Similarly, yr+1 gives r x m(m-1)/2. So in total we get m(m-1)/2 (1 + 2 + ... + n-1) = mn(m-1)(n-1)/4.
© John Scholes
jscholes@kalva.demon.co.uk
15 Feb 2002