20th Putnam 1959 Problem B1 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
: mn(m-1)(n-1)/4. Let us call the points on the y-axis y 1 < y 2 < ... < y n and the points on the x-axis x 1 < x 2 < ... < x m . Let us join first y 1 to each x i , then y 2 and so on. Joining y 1 to each of the x i creates no intersections. Joining y 2 to x 1 creates m-1 intersections. Joining it to x 2 creates m-2 intersections and so on. So, in all, joining y 2 gives 1 + 2 + ... + m-1 = m(m-1)/2 intersections. Similarly joining y 3 to x 1 gives 2(m-1) intersections. Joining it to x 2 gives 2(m-2) and so on. So, in all, y 3 gives 2 x m(m-1)/2. Similarly, y r+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. 20th Putnam 1959 © John Scholes jscholes@kalva.demon.co.uk 15 Feb 2002