CTK Exchange
Front Page
Movie shortcuts
Personal info
Awards
Reciprocal links
Terms of use
Privacy Policy

Interactive Activities

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

Manifesto: what CTK is about Search CTK Buying a book is a commitment to learning Table of content Things you can find on CTK Chronology of updates Email to Cut The Knot Recommend this page

CTK Exchange

Subject: "difficult sequence, areas partitioned in circle ,"     Previous Topic | Next Topic
Printer-friendly copy     Email this topic to a friend    
Conferences The CTK Exchange College math Topic #546
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 2
for n=3 you have 7 areas. for n=4 you have 16
the sequence emerges
1,2,7, 16,31,54, ...
I dont see any pattern or recurrence.


  Alert | IP Printer-friendly page | Reply | Reply With Quote | Top

  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)
Click to EMail mr_homm Click to send private message to mr_homm Click to view user profileClick to add this user to your buddy list  
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


  Alert | IP Printer-friendly page | Reply | Reply With Quote | Top
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 is
1,2,7,16,31,54...


  Alert | IP Printer-friendly page | Reply | Reply With Quote | Top
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) ).



  Alert | IP Printer-friendly page | Reply | Reply With Quote | Top
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.

https://www.cut-the-knot.org/books/dorrie/content.shtml


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 +1
R(2) = R(1) +2
R(3) = R(2) +3
.....

R(N) = R(N-1) +N

The addition of the above will yield to: R(N) = 1 + ( 1+2+3+�+N) and therefore

R(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.


  Alert | IP Printer-friendly page | Reply | Reply With Quote | Top
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.


  Alert | IP Printer-friendly page | Reply | Reply With Quote | Top
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.


  Alert | IP Printer-friendly page | Reply | Reply With Quote | Top
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


  Alert | IP Printer-friendly page | Reply | Reply With Quote | Top
mr_homm
Member since May-22-05
Dec-09-05, 05:16 PM (EST)
Click to EMail mr_homm Click to send private message to mr_homm Click to view user profileClick to add this user to your buddy list  
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


  Alert | IP Printer-friendly page | Reply | Reply With Quote | Top
Pierre Charland
Member since Dec-22-05
Jan-18-06, 08:04 AM (EST)
Click to EMail Pierre%20Charland Click to send private message to Pierre%20Charland Click to view user profileClick to add this user to your buddy list  
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)/2

where (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)/8

giving 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.54

AlphaChapMtl


  Alert | IP Printer-friendly page | Reply | Reply With Quote | Top
mr_homm
Member since May-22-05
Jan-18-06, 08:53 PM (EST)
Click to EMail mr_homm Click to send private message to mr_homm Click to view user profileClick to add this user to your buddy list  
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


  Alert | IP Printer-friendly page | Reply | Reply With Quote | Top
Pierre Charland
Member since Dec-22-05
Jan-20-06, 08:59 PM (EST)
Click to EMail Pierre%20Charland Click to send private message to Pierre%20Charland Click to view user profileClick to add this user to your buddy list  
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)/8

giving 1, 2, 7, 22, 56, 121, 232, 407, 667, 1036, 1541, 2212, ...


AlphaChapMtl


  Alert | IP Printer-friendly page | Reply | Reply With Quote | Top
Pierre Charland
Member since Dec-22-05
Jan-20-06, 08:59 PM (EST)
Click to EMail Pierre%20Charland Click to send private message to Pierre%20Charland Click to view user profileClick to add this user to your buddy list  
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

Attachments
https://www.cut-the-knot.org/htdocs/dcforum/User_files/43d1927d0f4dbd10.jpg

  Alert | IP Printer-friendly page | Reply | Reply With Quote | Top
mr_homm
Member since May-22-05
Jan-21-06, 11:53 AM (EST)
Click to EMail mr_homm Click to send private message to mr_homm Click to view user profileClick to add this user to your buddy list  
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)/8

This 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


  Alert | IP Printer-friendly page | Reply | Reply With Quote | Top
Pierre Charland
Member since Dec-22-05
Jan-22-06, 10:38 PM (EST)
Click to EMail Pierre%20Charland Click to send private message to Pierre%20Charland Click to view user profileClick to add this user to your buddy list  
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 is

2, 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 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.

AlphaChapMtl


  Alert | IP Printer-friendly page | Reply | Reply With Quote | Top
mr_homm
Member since May-22-05
Jan-23-06, 11:02 AM (EST)
Click to EMail mr_homm Click to send private message to mr_homm Click to view user profileClick to add this user to your buddy list  
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


  Alert | IP Printer-friendly page | Reply | Reply With Quote | Top

Conferences | Forums | Topics | Previous Topic | Next Topic

You may be curious to have a look at the old CTK Exchange archive.
Please do not post there.

|Front page| |Contents|

Copyright © 1996-2018 Alexander Bogomolny

Search:
Keywords:

Google
Web CTK