Dividing a Plane
Source: Concrete Mathematics, Donald Knuth
Problem:
Let's say we have a plane. Draw N straight lines on the plane, any way you wish. Try to divide the plane into as many different regions as possible. How many regions is that? For example, if we draw 1 line on the plane, we can divide it into two regions. If we draw 2 lines, we can divide it into four regions.
Followup questions:
Source: http://skepticsplay.blogspot.com/
Draw N perfect circles on a plane, of any size, anywhere you want. Into how many regions can you divide the plane? Next, draw N perfect ellipses on another plane. Into how many regions can you divide the plane?
Problem:
Let's say we have a plane. Draw N straight lines on the plane, any way you wish. Try to divide the plane into as many different regions as possible. How many regions is that? For example, if we draw 1 line on the plane, we can divide it into two regions. If we draw 2 lines, we can divide it into four regions.
Followup questions:
Source: http://skepticsplay.blogspot.com/
Draw N perfect circles on a plane, of any size, anywhere you want. Into how many regions can you divide the plane? Next, draw N perfect ellipses on another plane. Into how many regions can you divide the plane?
The number of new regions created by introducing another line is equal to the number of parts this line has been partitioned into by the existing lines. So in the best case
ReplyDeleteRn = R(n-1) + n;
and R0 = 1. Which leads to the closed form exp, Rn=(n*(n+1)/2) + 1
For line, I got it to be [n(n+1)/2 + 1]
ReplyDeleteDenote the no. of parts made by n lines by f(n).
Then f(n+1) - f(n) = n+1.
Hence.
For circle and ellipse, similarly
n(n-1) + 2
for lines : n(n+1)/2 + 1
ReplyDeletefor ellipses and circles : n(n-1) + 2
denote the no. by f(n), then for lines:
f(n+1) - f(n) = n+1
and for circle :
f(n+1) - f(n) = 2n
An interesting approach for the first problem :
ReplyDeleteLet's take a point at infinity such that all lines meet at that point. (or if you wish, you can imagine via stereographic projections).
By euler's formula, for any planar graph we have v - e + r = 2.
Here v = C(n,2) + 1, e = n^2, hence r = n(n+1)/2 + 1
For n circles we have v = 2C(n,2), e = n * 2(n-1) => r = 2 + 2n(n-1) - n(n-1) = n^2 - n + 2
ReplyDeleteFor the ellipse we have :
ReplyDeletev = 4C(n,2)
e = 4n(n-1)
=> r = 2(n^2 - n + 1)
Another solution for the line problem : Number of regions = 1 + Number of points + Number of lines.
ReplyDeleteReasoning : Start with 1 region, with each line you increase the number by 1 and same for each point.
This approach can be used to easily solve a trickier problem : Given n points on a circle, you join each pair. What is the maximum number of regions?