Problem:
Let ℓA​ and ℓB​ be two distinct parallel lines. For positive integers m and n, distinct points A1​,A2​,A3​,…,Am​ lie on ℓA​, and distinct points B1​,B2​,B3​,…,Bn​ lie on ℓB​. Additionally, when segments Ai​Bj​​ are drawn for all i=1,2,3,…,m and j=1,2,3,…,n, no point strictly between ℓA​ and ℓB​ lies on more than 1 of the segments. Find the number of bounded regions into which this figure divides the plane when m=7 and n=5. The figure shows that there are 8 regions when m=3 and n=2
Solution:
Assume that the points A1​,A2​,A3​,…,Am​ and B1​,B2​,B3​,…,Bn​ lie in these orders on the lines ℓA​ and ℓB​, respectively, so that ℓA​ and ℓB​ together with the segments A1​B1​​ and Am​Bn​​ bound one region in the plane. Consider adding the other line segments Ai​Bj​​ one at a time. One of these line segments divides each of k regions into two regions where k−1 is the number of times Ai​Bj​ intersects another of these line segments at a point between ℓA​ and ℓB​. It follows that the final number of regions must be 1 plus 2 less than the number of line segments drawn plus the number of intersection points of these segments between ℓA​ and ℓB​. Because there is one intersection point for every set of 4 points {Ap​,Aq​,Br​,Bs​} with 1≤p<q≤m and 1≤r<s≤n, the total number of regions is
1+(m⋅n−2)+(2m​)(2n​)
Substituting m=7 and n=5 gives
1+(7⋅5−2)+(27​)(25​)=244
OR
For a fixed value of m≥2, let f(n) be the number of bounded regions for given values of n. Then f(1)=m−1. To obtain f(n) from f(n−1), notice that adding the segment Ai​Bn​​ creates 1+(m−i)(n−1) new regions, so adding Bn​ to ℓB​ creates
1+[1+(n−1)]+[1+2(n−1)]+⋯+[1+(m−1)(n−1)]=m+2(n−1)m(m−1)​
new regions as segments from the new point to the points on ℓA​ are drawn. Therefore
f(n)=f(n−1)+m+2(n−1)m(m−1)​.
Computing recursively when m=7 gives f(1)=6,f(2)=34,f(3)=83,f(4)=153, and f(5)=244, which is the requested number of regions.
\section*{OR}
Consider the graph whose vertices are A1​,A2​​,A3​,…,Am​,B1​,B2​,B3​,…,Bn​, and the intersections of the Ai​Bj​​ line segments, and whose edges follow the Ai​Bj​​,B1​Bn​​, or A1​Am​​ line segments. Then this graph has m vertices on line ℓA​,n vertices on line ℓB​, and p=(2m​)(2n​) vertices between the two lines for a total of m+n+p vertices. Vertices A1​ and Am​ each have degree n+1, and each vertex Ai​ for 1<i<n has degree n+2. Similarly, vertices B1​ and Bn​ each have degree m+1, and each vertex Bj​ for 1<j<n has degree m+2. Each vertex between lines ℓA​ and ℓB​ has degree 4 . Thus the total of all the degrees of the vertices in the graph is
m(n+2)−2+n(m+2)−2+4p=2(mn+m+n−2+2p)
Hence the number of edges in the graph is half of this number which is mn+m+n−2+2p.\
Euler's Formula gives the number of bounded regions for a planar graph as 1 more than the number of edges minus the number of vertices, which, in this case, is
(mn+m+n−2+2p)−(m+n+p)+1=mn+p−1
When m=7 and n=5, this equals 7⋅5+(27​)(25​)−1=244​.
The problems on this page are the property of the MAA's American Mathematics Competitions
