|
Draw n points on the circumference on a circle. Then connect all lines between all points on the circle. What is the maximum number of regions that the circle may be divided into?
Example: For the case n=3, you have a triangle inscribed in the center of the circle. The number of regions is thus 4. For the case n=4, you have a square with diagonals drawn, so that gets you 8.
I will tell you though that the answer is not 2^(n-1), but it is not complicated.
|
I think the answer is the (amount of faces of an n-complete graph) + n
I'll get back to you once i figure out the first part
EDIT: I dont think this is possible with my knowledge of graph theory, since # faces is ill-defined for non-planar graphs, and everything K_5 and above is nonplanar... and im stuck
|
oops -- within the circle.. hmm
|
for n = 5 you have
which has 11 faces. Plus the 5 imaginary ones on the outside, so 16 total.
2^4 + 1 = 17
|
I don't know if there is a good graph theory solution, but my solution for this does not use any. You need to find a clever way to count the regions.
Also note that the number of regions for n=7 is 57 so looking for some sort of 2^something formula is not going to work.
|
|
# VERTICES | # EDGES | # FACES 3 | 3 | 1 + 3 = 4 4 | 6 | 4 + 4 = 8 5 | 10 | 11 + 5 = 16 6 | 15 | 24 + 6 = 30 7 | 21 | 50 + 7 = 57
For anyone else attempting a graph-theory approach
|
|
|
@complete + Show Spoiler +I think that is the correct answer, though you should realize that you can express it in a more elegant form (namely as the sum of binomial coefficients. What is your reasoning/how did you get the answer? Did you assume it was a polynomial and interpolated?
|
It looks to me like he graphed the first couple of n's and then used software to fit the data but thats just a guess
|
+ Show Spoiler +C(n, 4) + C(n, 2) + 1 Number of lines drawn between n points can be expressed as a series (n-1)+(n-2)+...(n-(n-1)) Or more practical as binomial coefficient: C(n,2). Expressing number of possibilities to connect 2 points in an n point circle by a line. C(n,4) gives the number of possible intersects between any 4 of the n points in the circle. Adding them together and the extra region in the center (+1), gives you the total. + Show Spoiler +Watched the spoilers for help....
|
@LaluSh
+ Show Spoiler +That is the correct answer Can you justify why your answer is correct though? As in why should counting these intersections give you the number of regions?
|
+ Show Spoiler +Every time a line intersects another line, you bisect two regions into four regions
|
|
|
|