180 11. Combinatorics in Geometry
The first natural idea to solve this problem is the following: Count the
intersection points on each diagonal, and then add up these numbers. Let’s
follow through this method in the case of a hexagon (Figure 11.2). First
consider a diagonal which connects two second-neighboring vertices of the
hexagon, say these areAandC. This diagonalACintersects all three
diagonals that start inB, which means that there are three intersections
on the diagonalAC. There are six diagonals of this type, so altogether we
count 6·3 = 18 intersections.
ABC DEF ABC DEF ABC DEFFIGURE 11.2.Now consider a diagonal that connects two opposite vertices of the
hexagon, sayAD. One can see in the figure that there are four intersections
on this diagonal. We have three diagonals of this type, which means that
we get 3·4 = 12 further intersections.
Is it true that we have 18+12 = 30 intersections? We must be more care-
ful! The intersection of the diagonalsACandBDwas counted twice: Once
when we considered the intersections onAC, and also when we counted
the intersections onBD. The same holds for any other intersection too: we
counted all of them exactly twice. So we have to divide our result by 2, so
our final, correct result is 15, which can be easily checked in the figure.
One can see that already for the case of such a smalln,wehaveto
consider several cases, so our method is too complicated, even though it
can be carried through for arbitraryn(try it!). But we can find a much
more elegant enumeration of the intersections if we use our combinatorial
knowledge.
Label every intersection point by the endpoints of the diagonals inter-
secting at this point. For instance, the intersection of the diagonalsACand
BDgets the labelABCD, the intersection of the diagonalsADandCE
gets the labelACDE, and so on. Is this labeling good, by which we mean
that different intersection points get different labels? The labeling is good,
since the labelsA, B, C, Dare given only to the intersection of the diago-
nals of the convex quadrilateralABCD(ACandBD). Furthermore, every
set of 4 vertices are used to label an intersection point of the diagonals; for
instance, the 4-tupleACEFdenotes the intersection of the diagonalsAE
andCF(Figure 11.3).