wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> easy >> Points on a circle
        
(Message started by: jollytall on Apr 1st, 2014, 4:12am)
Title: Points on a circle
Post by jollytall on Apr 1st, 2014, 4:12am
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))?
Title: Re: Points on a circle
Post by rmsgrey on Apr 1st, 2014, 7:13am
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?
Title: Re: Points on a circle
Post by jollytall on Apr 1st, 2014, 8:22am
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 :-)
Title: Re: Points on a circle
Post by towr on Apr 1st, 2014, 10:58pm
n=6: [hide]31[/hide]
n=7: [hide]57[/hide]

therefore
[hide]http://oeis.org/A000127[/hide] (http://oeis.org/A000127)
Title: Re: Points on a circle
Post by jollytall on Apr 1st, 2014, 11:26pm
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.
Title: Re: Points on a circle
Post by rloginunix on Apr 2nd, 2014, 9:14am
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.
Title: Re: Points on a circle
Post by rmsgrey on Apr 3rd, 2014, 7:19am

on 04/02/14 at 09:14:54, 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, ...
Title: Re: Points on a circle
Post by rloginunix on Apr 3rd, 2014, 5:20pm
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 ...
Title: Re: Points on a circle
Post by rloginunix on Apr 5th, 2014, 12:59pm
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.
Title: Re: Points on a circle
Post by Annettagiles on Oct 23rd, 2014, 4:53am
may be n(n-1)
Title: Re: Points on a circle
Post by Grimbal on Oct 23rd, 2014, 6:44am

on 10/23/14 at 04:53:13, Annettagiles wrote:
may be n(n-1)

That would be the number of lines, not the number of regions.


Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board