CTK Exchange Front Page Movie shortcuts Personal info Awards Reciprocal links Terms of use Privacy Policy Cut The Knot! MSET99 Talk Games & Puzzles Arithmetic/Algebra Geometry Probability Eye Opener Analog Gadgets Inventor's Paradox Did you know?... Proofs Math as Language Things Impossible My Logo Math Poll Other Math sit's Guest book News sit's Recommend this site        CTK Exchange

 Subject: "difficult sequence, areas partitioned in circle ," Previous Topic | Next Topic
 Conferences The CTK Exchange College math Topic #546 Printer-friendly copy Email this topic to a friend Reading Topic #546
tommy guest
Dec-07-05, 00:46 AM (EST)

"difficult sequence, areas partitioned in circle ,"

 THe question is the opposite of the famous one.Take a circle, put on the inside of the circle (not on the circumference) any n points no three collinear. Make a chord between any two points. How many areas are partitioned by the chords. For n=1 , you have one area, n=2 you have 2for n=3 you have 7 areas. for n=4 you have 16 the sequence emerges1,2,7, 16,31,54, ... I dont see any pattern or recurrence.

Subject     Author     Message Date     ID difficult sequence, areas partitioned in circle , tommy Dec-07-05 TOP RE: difficult sequence, areas partitioned in circle , mr_homm Dec-07-05 2 RE: difficult sequence, areas partitioned in circle , tommy` Dec-09-05 3 RE: difficult sequence, areas partitioned in circle , mpdlc Dec-18-05 8 RE: difficult sequence, areas partitioned in circle , mpdlc Dec-21-05 9 RE: difficult sequence, areas partitioned in circle , tommy Dec-09-05 4 RE: difficult sequence, areas partitioned in circle , tommy Dec-09-05 5 RE: difficult sequence, areas partitioned in circle , tommy Dec-09-05 6 RE: difficult sequence, areas partitioned in circle , mr_homm Dec-09-05 7 RE: difficult sequence, areas partitioned in circle , Pierre Charland Jan-18-06 10 RE: difficult sequence, areas partitioned in circle , mr_homm Jan-18-06 11 RE: difficult sequence, areas partitioned in circle , Pierre Charland Jan-20-06 12 RE: difficult sequence, areas partitioned in circle , Pierre Charland Jan-20-06 13 RE: difficult sequence, areas partitioned in circle , mr_homm Jan-21-06 14 RE: difficult sequence, areas partitioned in circle , Pierre Charland Jan-22-06 15 RE: difficult sequence, areas partitioned in circle , mr_homm Jan-23-06 16

 Conferences | Forums | Topics | Previous Topic | Next Topic
mr_homm
Member since May-22-05
Dec-07-05, 04:47 PM (EST)    2. "RE: difficult sequence, areas partitioned in circle ,"
In response to message #0

 I don't think that this question has a unique answer, at least as it was stated. For instance, if I take 4 points forming a perfect square concentric with the circle, there will be 9 regions (like a tic-tac-toe board), but if I tilt the two vertical sides until their point of intersection of comes inside the circle, I will get 10 regions, and if I do the same for the horizontal sides as will, 11 regions.Therefore, the number of regions depends on the exact arrangement of the points. If you are looking for the maximum number of partitions, then moving the points very near the center (or equivalently, making the circle very large) so that all the intersection points are within the circle will give the largest number of regions. In that case, it is best to simply push the circle out to infinity and ask how many regions the whole plane is cut into by lines joining pairs of points.Even if no three points are collinear, it is still possible to have coincidences where two lines are parallel, or more than two lines are concurrent at a common point. These cases will reduce the number of regions, and so if you want the maximum, these must also be excluded. In this case, you are assuming that the lines are in general position, so you don't need to say anything about the original set of n points, except that n points will determine n(n-1)/2 lines.Therefore, this is a special case of the more general problem: how many regions is the plane cut into by m lines in general position? Setting m = n(n-1)/2 would then give the solution to your problem.--Stuart Anderson tommy` guest
Dec-09-05, 08:53 AM (EST)

3. "RE: difficult sequence, areas partitioned in circle ,"
In response to message #2

 No. I am asking about the areas partitioned, not the number of lines. Let me rephrase the question. Let's say you have 3 randomly points placed interior or inside a circle . The three non collinear points will determine 3 chords inside the circle if I draw lines connecting every two points. A chord is a line drawn inside a circle which stops at the circumference. Now two points determine a chord. So 3 points will make 3 chords. I am not asking about the number of lines, I am asking about the areas partitioned. For 3 points I get 7 areas are partitioned. Please try this. Draw a circle, place 3 points. Try chords connecting the dots. So you should get get 7 areas for 3 chords. The sequence starts with 1 because 1 point has 1 area partitioned, 2 points make 1 chord which gives you 2 areas partitioned, etc so How many areas are partioned in the circle given n points (any 3 non collinear) and chords drawn through any 2 points. The sequence is1,2,7,16,31,54... mpdlc guest
Dec-18-05, 09:39 AM (EST)

8. "RE: difficult sequence, areas partitioned in circle ,"
In response to message #3

 Browsing the CTK I found your question, and after the clear explanation given by Stuart you probably got the number of regions as stated depends on the size of radius of the circumference. Another good example, is taking five points the pentagon area beyond the edges of the five points star can be or not within the circle.However I think as an interesting alterative to your problem you can try to get the maximum number of regions that we can form taking the N points p1, p2.....pN within a circle (C), and connecting them with circumferences. All circumferences will contain the center O of the original circle (C), and any pair of points: ( Op1p2; Op1p3; ...Op1pN,...Op2p3,Op2p4...Op(N-1)p(N) ). mpdlc guest
Dec-21-05, 11:05 AM (EST)

9. "RE: difficult sequence, areas partitioned in circle ,"
In response to message #8

 Hi Tommy,Not willing to pose a question and later not answering it and as a follow-up of my remarks, I must add the following.My proposal was to get the maximum number of regions that we can form taking the N points p1, p2.....pN within a circle (C), and connecting them with circumferences. All circumferences will contain the center O of the original circle (C), and any pair of points: ( Op1p2; Op1p3; ...Op1pN,...Op2p3,Op2p4...Op(N-1)p(N) ).This problem come out to be the same as getting the maximum amount of regions it can be form by laying in a plane N straight line, since by virtue of an inversion using as circle of inversion (C) the circumferences all containing the center O will been transformed in straight lines not passing by O. Therefore is the same problem that Stuart suggested in the last paragraph of his remarks. Obviously calling N the number of straight lines, N equals to n(n-1)/2, being n the number of points. So if you are still interested the answer follows below.I do remember from my late HS year to been taught how to solved this problem by induction using the formulae for arithmetic progression of a second order is elegant and can be extrapolated to the maximum number of regions that can be divided a nD space by hyper-planes, I believe the method belongs to Professor Polya. Obviously it will include the division of a 3D space using planes which is known by Steiner�s problem and which is referred in article 67 of Heinrich Dorrie book, as a preliminary problem the article solves the division of the plane by N straight lines.Since the explanation by arithmetic progression of a second order require using combinatory notation, and my word processor is not fitted for the job, I will just summarize synthetically the content of the article referred to our case.Assuming that our plane is divided by N lines in R(N) regions if we draw an additional line, this particular line not being parallel to any of the existing ones will cut the N existing lines in N points and thus will transverse N+1 of all existing regions, those regions will become divided in two parts, so the new number of region R(N+1) will obey the difference equation:R(N+1) = R(N) + (N+1) which is easily solved as follow :R(1) = 1 +1R(2) = R(1) +2R(3) = R(2) +3.....R(N) = R(N-1) +NThe addition of the above will yield to: R(N) = 1 + ( 1+2+3+�+N) and thereforeR(N) = 1 + N( N+1)/2. So since N=n(n-1)/2 all we have to do is to substitute N in term of n if our data are the number of points. tommy guest
Dec-09-05, 08:53 AM (EST)

4. "RE: difficult sequence, areas partitioned in circle ,"
In response to message #2

 Maybe my mistake was the word partition. THis means to me, areas sectioned off. So for three points and 3 chords, you get 7 areas cut off in total. tommy guest
Dec-09-05, 08:53 AM (EST)

5. "RE: difficult sequence, areas partitioned in circle ,"
In response to message #2

 the trick is, the points determining the chords have to be inside the circle, not outside. the points are interior the circle. try it . draw 4 points inside a circle any three non collinear. you should get 6 chords, and 16 areas. the point of the sequence is the number of areas cut off. tommy guest
Dec-09-05, 08:53 AM (EST)

6. "RE: difficult sequence, areas partitioned in circle ,"
In response to message #2

 your tic tac toe example was flawed because you still get 16 areas partitioned if you connect every two points with a chord. you didnt connect the inside square points. You should get two diagonals that go through the tic tac toe if you are forming a straight tic tac toe diagram mr_homm
Member since May-22-05
Dec-09-05, 05:16 PM (EST)    7. "RE: difficult sequence, areas partitioned in circle ,"
In response to message #6

 I did understand that you were talking about counting the regions not the lines, so that's OK. You were right that I forgot the two crossing lines in my tic-tac-toe example, but I think that what I said there is still true: by changing the positions of the points, you can change the number of regions that the circle is cut into, therefore there is no unique answer to your question.For 3 points, I agree that you must get 7 regions, but for 4 points, you must get 16, 17, or 18 regions depending on how your points are arranged. For example, if you take the circle to be x2 + y2 = 1 and let the 4 points be (x,y) = (-0.1,-0.1), (-0.1,0.1), (0.1,-0.1), (0.1,0.1), you will get a tic-tac-toe board with a cross through the center, which gives 16 regions. BUT, if you let the 4 points be (x,y) = (-0.2,-0.1), (-0.1,0.1), (0.2,-0.1), (0.1,0.1), the lines that were vertical in the original tic-tac-toe shape will now meet at (0,0.3), and a new region will appear above this point, making the total 17 regions. You can also distort the positions of the points so that the lines that were horizontal in the original tic-tac-toe shape will now meet inside the circle, so you can get 18 regions.I am sorry that I forgot the two diagonal lines in my original tic-tac-toe example, as this made my point less clear. I think that if you draw what I described you will see that you get different numbers of regions depending on how the 4 points are arranged. Notice that no three of these points are collinear, so they still satisfy your original requirements.Notice that this does not depend on the original lines being parallel, as they were in the tic-tac-toe example. If you have two pairs of points inside the circle, and they define lines that are nearly parallel, then the meeting point of these lines could lie outside the circle. Then moving the points slightly to change the angles of the lines could being this meeting point inside the circle, where it would cause one more region to appear.That is why I said before that the circle gives trouble. If you just wanted to cut the whole plane into regions using the lines defined by n points, then none of this trouble could happen, because all intersection points would be included automatically, instead of some being inside the circle and others outside it. You would still have trouble with parallel lines, because they would cut the plane into fewer regions than non-parallel lines. In fact, the example I gave here with the point coordinates shows that the whole plane would be cut into 16 regions with the first set of points, and into 17 regions with the second set of points.Therefore, to get a definite number, you have to disallow parallel lines. It is also possible for several lines to meet at a common point, which would reduce the number of regions the plane (or circle) was cut into. For example, it you added to my original 4 points in the example above, another two points at (x,y) = (0,-0.5), (0,0.5), they would generate several more lines with the other points, but one particular line would give trouble: the line joining the new pair of points will meet the original pair of diagonal lines at the origin, so that three lines are concurrent there. Now if I move the new pair of points a tiny bit to the right, so they are now (0.0001,-0.5), (0.0001, 0.5), the line joining them will miss the origin by a little bit, and there will be a tiny triangle contained between it and the two diagonals, which was not there before. None of the other regions will be affected by this (draw it to see), so the total number of regions will be increased by 1 when I move these points.This means that to get a definite answer, you must require that none of the lines are concurrent, none are parallel, and there is no circle. In that case, your n points will generate n(n-1)/2 lines, and as I said before, the problem becomes one of finding how many regions the plane is cut into by n(n-1)/2 lines that are in general position (i.e., none parallel, none concurrent).I hope this is more clear than my earlier post.Good luck in solving this problem.--Stuart Anderson Pierre Charland
Member since Dec-22-05
Jan-18-06, 08:04 AM (EST)    10. "RE: difficult sequence, areas partitioned in circle ,"
In response to message #7

 Finding how many regions the plane is cut into by k lines that are in general position? The answer is: (k,0) + (k,1) + (k,2) = (k^2+k+2)/2where (a,b) is a binomial coefficient.If k=n(n-1)/2 then((n(n-1)/2)^2+(n(n-1)/2)+2)/2 = (n^4-2n^3+3n^2-2n+8)/8giving 1, 2, 7, 18, 56, ...Ref:-- Ivan Niven, Mathematics of Choice p.124-126-- David Wells, Curious and Interesting Puzzles, 464 p.146-- H. Dorrie, 100 Great Problems of Elementary Math... p.283-- Martin Gardner, New Mathematical Diversions, p.236, p.242-- Ross Honsberger, Mathematical Gems I, 12.1 p.134-- G. Polya, Mathematics and Plausible Reasoning Vol.I, p.47, 3.11 p.54AlphaChapMtl mr_homm
Member since May-22-05
Jan-18-06, 08:53 PM (EST)    11. "RE: difficult sequence, areas partitioned in circle ,"
In response to message #10

 Hello Pierre Charland,I had spent some time making Tommy's original question into something more definite that could be solved, but I never actually tried to solve it. Thank you for finding and presenting the solution. It is interesting to see that the number of regions is growing like a polynomial. Without seeing your solution, I might have thought that the number would grow exponentially, because at the beginning each new line cuts all the previous regions, which doubles the number. Of course, when there are already many regions, a new line will only cut a few of then, so the growth is not so fast -- polynomial becomes more plausible then.Thank you,Stuart Anderson Pierre Charland
Member since Dec-22-05
Jan-20-06, 08:59 PM (EST)    12. "RE: difficult sequence, areas partitioned in circle ,"
In response to message #11

 CORRECTION: 18 should be 22 in my previous answer,(I can't do anything without my calculator!)If k=n(n-1)/2 then((n(n-1)/2)^2+(n(n-1)/2)+2)/2 = (n^4-2n^3+3n^2-2n+8)/8giving 1, 2, 7, 22, 56, 121, 232, 407, 667, 1036, 1541, 2212, ...AlphaChapMtl Pierre Charland
Member since Dec-22-05
Jan-20-06, 08:59 PM (EST)    13. "RE: difficult sequence, areas partitioned in circle ,"
In response to message #11

 But I think there is a problem,I can't find 22 regions for n=4.So the reasonning leading to the formula must be wrong.AlphaChapMtl mr_homm
Member since May-22-05
Jan-21-06, 11:53 AM (EST)    14. "RE: difficult sequence, areas partitioned in circle ,"
In response to message #13

 Hello Pierre Charland,>But I think there is a problem, >I can't find 22 regions for n=4. >So the reasonning leading to the formula must be wrong. The error was mine. In my earlier post, I said that the problem was to find the number of regions for n(n-1)/2 lines in general position. However, what I meant to say was that the lines were in general position, EXCEPT at the original set of n points which determined the lines.At the original points, there are n-1 concurrent lines, so of course this is not general position. You can account for the change in the number of regions like this:For each of the original n points, place a small circle around it, small enough that none of the other points is inside the circle. Then displace the lines slightly to remove the concurrence, i.e. put the n-1 lines into general position inside this circle. Now the area inside the circle will be cut into (n-1,0) + (n-1,1) + (n-1,2) regions, according to your formula. However, when the lines were concurrent, they cut this circle into 2(n-1) regions, like slicing a round pie through the center. The difference between these numbers is the number of regions which are removed by the concurrency.Since (n-1,0) + (n-1,1) + (n-1,2) - 2(n-1) = (n-2)(n-3)/2, the total loss of regions for all n points is n(n-2)(n-3)/2. This formula is true only for n > 1, since for n = 0 or 1, the binomial coefficient formula is not valid. However, for n <= 3 there are at most 2 lines through each point, and so the lines truly are in general position. This is shown also by the fact that the correction vanishes at n = 2 or n = 3.Therefore, subtracting the correction from the formula you gave for lines in general position, we get the new polynomial (n^4 - 2n^3 + 3n^2 - 2n + 8)/8 - (n^3 - 5n^2 + 6n)/2 =(n^4 -6n^3 + 23n^2 +22n +8)/8This should be correct now. To check, the correction for n = 4 is 4(2)(1)/2 = 4, which reduces the region count from 22 to 18 as it'should.I think this clears up the problem. Sorry for the original unclear formulation.--Stuart Anderson Pierre Charland
Member since Dec-22-05
Jan-22-06, 10:38 PM (EST)    15. "RE: difficult sequence, areas partitioned in circle ,"
In response to message #14

 Wow, that's good reasoning!I though it would be more difficult to correct those problems.This is an interesting variation.So you are right, we do get(n^4 - 2n^3 + 3n^2 - 2n + 8)/8 - (n^3 - 5n^2 + 6n)/2 = (n^4 -6n^3 + 23n^2 -26n +8)/8< not = (n^4 -6n^3 + 23n^2 +22n +8)/8 >For n=2 to 14, this is2, 7, 18, 41, 85, 162, 287, 478, 756, 1145, 1672, 2367, 3263, ..I checked on a drawing for n=5 and there are 41 regions.Good work.------------------------------------------------------PS: After all this, (that is after I got your answer),I searched "7,18,41,85" on Googleand found it in the Encyclopedia of Integer Sequences(It is not in the printed version I have)https://www.research.att.com/~njas/sequences/A055503where the following reference is given:L. Comtet, Advanced Combinatorics, Reidel, 1974, Problem 1, p. 72; and Problem 8, p. 74. AlphaChapMtl mr_homm
Member since May-22-05
Jan-23-06, 11:02 AM (EST)    16. "RE: difficult sequence, areas partitioned in circle ,"
In response to message #15

 Hello Pierre Charland,>(n^4 - 2n^3 + 3n^2 - 2n + 8)/8 - (n^3 - 5n^2 + 6n)/2 > = (n^4 -6n^3 + 23n^2 -26n +8)/8 >>< not = (n^4 -6n^3 + 23n^2 +22n +8)/8 > Oops! You are right of course; I seem to have had a little sign error in the final polynomial.>Good work. Thanks!>>------------------------------------------------------ >PS: After all this, (that is after I got your answer), >I searched "7,18,41,85" on Google >and found it in the Encyclopedia of Integer Sequences >(It is not in the printed version I have) >>https://www.research.att.com/~njas/sequences/A055503 >where the following reference is given: >L. Comtet, Advanced Combinatorics, Reidel, 1974, Problem 1, >p. 72; and Problem 8, p. 74. I've never used this encyclopedia, although I've heard others here speak of it. It looks like a useful tool, especially since Google can search it online.This wraps up the question that started this thread, then, so now I'll go looking around for other fun questions. Thanks for an interesting discussion.--Stuart Anderson

 Conferences | Forums | Topics | Previous Topic | Next Topic
 Select another forum or conference Lobby The CTK Exchange (Conference)   |--Early math (Public)   |--Middle school (Public)   |--High school (Public)   |--College math (Public)   |--This and that (Public)   |--Guest book (Public) Educational Press (Conference)   |--No Child Left Behind (Public)   |--Math Wars (Public)   |--Mathematics and general education (Public) You may be curious to have a look at the old CTK Exchange archive.  