Author |
Topic: Points on a circle (Read 1810 times) |
|
jollytall
Senior Riddler
Gender: 
Posts: 585
|
 |
Points on a circle
« on: Apr 1st, 2014, 4:12am » |
 Quote  Modify
|
And one for today.
If you take a circle and make on its perimeter one point, it does not cut the circle, so you have one piece.
If you make 2 points on the perimeter and connect them, it cuts the circle into 2.
Etc.
What is the formula for n? (n different points on the perimeter and connect all of them. How many pieces do you cut the circle (the shape, not the perimeter))?
|
|
 IP Logged |
|
|
|
rmsgrey
Uberpuzzler
    
Gender:
Posts: 2873
|
|
Re: Points on a circle
« Reply #1 on: Apr 1st, 2014, 7:13am » |
Quote Modify
|
n=1: 1 region
n=2: 2 regions
n=3: 4 regions
n=4: 8 regions
n=5: 16 regions
I'd have to draw out n=6 in order to count it, so I'll stop there and let someone else finish this one.
Also, there's a potential anomaly with n>5 where you can have three (or more) lines intersecting at a single point - do you count the trivial regions formed or not?
|
|
IP Logged |
|
|
|
jollytall
Senior Riddler
Gender:
Posts: 585
|
|
Re: Points on a circle
« Reply #2 on: Apr 1st, 2014, 8:22am » |
Quote Modify
|
I should have added "max" number of regions, indeed to avoid the null-area cuts.
I think 1, 2, 4, 8, 16 might raise some ideas for the formula, but let's see 
|
|
IP Logged |
|
|
|
jollytall
Senior Riddler
Gender:
Posts: 585
|
|
Re: Points on a circle
« Reply #4 on: Apr 1st, 2014, 11:26pm » |
Quote Modify
|
Indeed. The point was on 1/April to show how foolish it can be to look at the first few (5 in this case) elements of a series and guess the rest from there.
|
|
IP Logged |
|
|
|
rloginunix
Uberpuzzler
Posts: 1029
|
|
Re: Points on a circle
« Reply #5 on: Apr 2nd, 2014, 9:14am » |
Quote Modify
|
I waited until April 2-nd rolls around in my time zone (because today will be yesterday tomorrow) to say that there's still a little bit of a saving grace here: the number of line segments formed by the points placed as the problem statement describes:
0, 1, 3, 6, 10, 15, 21, 28, 36, 45
Since every time we add the n-th point we keep all the previously constructed line segments we are really adding (n - 1) new line segments to the mix and since AB and BA designate the same line segment we divide the total by two:
n(n - 1)/2
that is if the sequence starts at n = 1, meaning 1 point on the circumference. If this familiar sequence starts at n = 0 then it would be n(n + 1)/2.
|
|
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
Gender:
Posts: 2873
|
|
Re: Points on a circle
« Reply #6 on: Apr 3rd, 2014, 7:19am » |
Quote Modify
|
on Apr 2nd, 2014, 9:14am, rloginunix wrote:I waited until April 2-nd rolls around in my time zone (because today will be yesterday tomorrow) to say that there's still a little bit of a saving grace here: the number of line segments formed by the points placed as the problem statement describes:
0, 1, 3, 6, 10, 15, 21, 28, 36, 45
Since every time we add the n-th point we keep all the previously constructed line segments we are really adding (n - 1) new line segments to the mix and since AB and BA designate the same line segment we divide the total by two:
n(n - 1)/2
that is if the sequence starts at n = 1, meaning 1 point on the circumference. If this familiar sequence starts at n = 0 then it would be n(n + 1)/2. |
|
There are several ways of counting line segments - if you allow intersections to break up lines, then you get a higher number of distinct line segments (for n>3):
0, 1, 3, 8, 20, ...
|
|
IP Logged |
|
|
|
rloginunix
Uberpuzzler
Posts: 1029
|
|
Re: Points on a circle
« Reply #7 on: Apr 3rd, 2014, 5:20pm » |
Quote Modify
|
My patience was good for only n = 6, n = 7 and n = 8.
For n = 6 I've got 6 + 6*4 + 3*5 = 45. For n = 7 I've got 8*7 + 7*5 = 91. For n = 8 I've got 8 + (6 + 9 + 10 + 9 + 6)*4 = 168.
So first few integers are:
0, 1, 3, 8, 20, 45, 91, 168
Applying the method of finite differences we get:
0, 1, 3, 8, 20, 45, 91, 168
1 2 5 12 25 46 77
1 3 7 13 21 31
2 4 6 8 10
2 2 2 2
So it must be a polynomial of the 4-th degree:
f(n) = 0*C(n - 1, 0) + 1*C(n - 1, 1) + 1*C(n - 1, 2) + 2*C(n - 1, 3) + 2*C(n - 1, 4)
C(n - 1, 0) = 1
C(n - 1, 1) = n - 1
C(n - 1, 2) = (n - 1)(n - 2)/2
C(n - 1, 3) = (n - 1)(n - 2)(n - 3)/6
C(n - 1, 4) = (n - 1)(n - 2)(n - 3)(n - 4)/24
f(n) = n - 1 + (n - 1)(n - 2)/2 + (n - 1)(n - 2)(n - 3)/3 + (n - 1)(n - 2)(n - 3)(n - 4)/12
f(n) = (12n - 12 + 6(n - 1)(n - 2) + 4(n - 1)(n - 2)(n - 3) + (n - 1)(n - 2)(n - 3)(n - 4))/12
Someone else please finish this. I am going blind ...
|
|
IP Logged |
|
|
|
rloginunix
Uberpuzzler
Posts: 1029
|
|
Re: Points on a circle
« Reply #8 on: Apr 5th, 2014, 12:59pm » |
Quote Modify
|
f(n) = (n^4 - 6n^3 + 17n^2 - 12n)/12 = n(n(n(n - 6) + 17) - 12)/12
With the help of a C program here's a few more terms:
0, 1, 3, 8, 20, 45, 91, 168, 288, 465, 715, 1056, 1508, 2093, 2835, 3760, 4896, 6273, 7923, 9880
If we throw out zero then the main diagonal becomes 1, 2, 3, 4, 2 and if we start with n = 1 then f(n) = (n^4 - 2n^3 + 5n^2 + 8n)/12 = n(n(n(n - 2) + 5) + 8)/12.
If we start with n = 0 then
C(n, 0) = 1
C(n, 1) = n
C(n, 2) = n(n - 1)/2
C(n, 3) = n(n - 1)(n - 2)/6
C(n, 4) = n(n - 1)(n - 2)(n - 3)/24
and f(n) = 1 + 2n + 3n(n - 1)/2 + 4n(n - 1)(n - 2)/6 + 2n(n - 1)(n - 2)(n - 3)/24 or
f(n) = (n^4 + 2n^3 + 5n^2 + 16n + 12)/12 = (n(n(n(n + 2) + 5) + 16) + 12)/12
I ran my C program for all three cases - the terms are all the same except for 0.
|
|
IP Logged |
|
|
|
Annettagiles
Junior Member
Gender:
Posts: 67
|
|
Re: Points on a circle
« Reply #9 on: Oct 23rd, 2014, 4:53am » |
Quote Modify
|
may be n(n-1)
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Points on a circle
« Reply #10 on: Oct 23rd, 2014, 6:44am » |
Quote Modify
|
on Oct 23rd, 2014, 4:53am, Annettagiles wrote:
That would be the number of lines, not the number of regions.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print