15th Putnam 1955 Problem A4 n vertices are taken on a circle and all possible chords are drawn. No three chords are concurrent (except at a vertex). How many points of intersection are there (excluding vertices)? Solution
: nC4. Easy. Every 4 vertices correspond to a unique point of intersection (the intersection of the two diagonals defined by the 4 points). [Actually, I got this the hard way. Take one of the vertices. Consider the diagonals from it. The diagonal to the next vertex but one has one vertex on one side and (n - 3) on the other. So it has 1(n - 3) points of intersection on it. The next diagonal has 2(n - 4) and so on up to (n - 3)1. We repeat for each vertex. That gives a total of n[1(n - 3) + 2(n - 4) + ... + (n - 3)1] points of intersection. But we count each diagonal twice and then each point of intersection twice. So the number of points of intersection is n/4 ∑ 1 n-3 r(n - 2 - r) = n/4 [ (n - 2) 1/2 (n - 3)(n - 2) - 1/6 (n - 3)(n - 2)(2n - 5) ] = 1/24 n(n - 2)(n - 3) [3(n - 2) - (2n - 5)] = nC4. Of course, at this point, one wonders why the answer has such a nice form!] 15th Putnam 1955 © John Scholes jscholes@kalva.demon.co.uk 26 Nov 1999