10213  How Many Pieces of Land ?
Moderator: Board moderators
10213  How Many Pieces of Land ?
Hey !
Pls inform what'll be the output for the following values of N ?
N=5,6,7,8,9,10,2147483647
Thanks in advanve.
Pls inform what'll be the output for the following values of N ?
N=5,6,7,8,9,10,2147483647
Thanks in advanve.
Hi~
There is a formula to solve this question, I don't know if it has a name, because I prove it myself by induction:
answer = (i  1) * i * (i * i  5 * i + 18) / 24 + 1
where i is the input (For i > 1)
<font size=1>[ This Message was edited by: .. on 20020120 07:55 ]</font>
There is a formula to solve this question, I don't know if it has a name, because I prove it myself by induction:
answer = (i  1) * i * (i * i  5 * i + 18) / 24 + 1
where i is the input (For i > 1)
<font size=1>[ This Message was edited by: .. on 20020120 07:55 ]</font>
Last edited by .. on Fri Jan 24, 2003 3:14 pm, edited 1 time in total.
oh......that is quite difficult to tell you the proof by text......hope you will understand what I say:
Let P(n) be the number of lands when n points are drawn on circle
Now assume knowing P(n1), want to know P(n) by adding the nth point
when the nth point draw a line to the kth point (1 <= k <= n1)
on the LHS on kth point, there is k1 points between kth and nth point
on the RHS on kth point, there is (n1)k+1 points between kth and nth point
the points in these 2 sets(LHS, RHS) are completely connected,
so there are (k1)*(nk) lines crossed by the newly drawn line,
creating (k1)*(nk)+1 new lands......
So, drawing lines from newly added nth point to all n1 old points,
will create
summation[(k1)(jk)+1] {k = 1..j (j = n1)} new lands
let says the summation be F(j)
P(n)= P(n1) + F(n1)
= P(n2) + F(n2) + F(n1)
.....
= P(0) + F(1) + F(2) + ....... + F(n1)
= 1 + summation(F(i)) {i = 1..n1}
by using formula of summation to simplify the equatoin(what a difficult job.....)
I get
answer = (i  1) * i * (i * i  5 * i + 18) / 24 + 1;
Good luck~
Let P(n) be the number of lands when n points are drawn on circle
Now assume knowing P(n1), want to know P(n) by adding the nth point
when the nth point draw a line to the kth point (1 <= k <= n1)
on the LHS on kth point, there is k1 points between kth and nth point
on the RHS on kth point, there is (n1)k+1 points between kth and nth point
the points in these 2 sets(LHS, RHS) are completely connected,
so there are (k1)*(nk) lines crossed by the newly drawn line,
creating (k1)*(nk)+1 new lands......
So, drawing lines from newly added nth point to all n1 old points,
will create
summation[(k1)(jk)+1] {k = 1..j (j = n1)} new lands
let says the summation be F(j)
P(n)= P(n1) + F(n1)
= P(n2) + F(n2) + F(n1)
.....
= P(0) + F(1) + F(2) + ....... + F(n1)
= 1 + summation(F(i)) {i = 1..n1}
by using formula of summation to simplify the equatoin(what a difficult job.....)
I get
answer = (i  1) * i * (i * i  5 * i + 18) / 24 + 1;
Good luck~
Last edited by .. on Fri Jan 24, 2003 3:15 pm, edited 1 time in total.
10213  How many pieces of land?
Hi all!
I was thinking in this problem and don't get the recurrence relation...
Can anyone help?
Thanks,
JP!
I was thinking in this problem and don't get the recurrence relation...
Can anyone help?
Thanks,
JP!

 Experienced poster
 Posts: 146
 Joined: Sat Apr 26, 2003 2:51 am
And how do I get it?
Ok, it appears to be right!
But, how do I get to this formula?
Thanks!
PS: I searched the board and did not found any topic on this problem, can you tell me where it is?
But, how do I get to this formula?
Thanks!
PS: I searched the board and did not found any topic on this problem, can you tell me where it is?

 Guru
 Posts: 834
 Joined: Wed May 29, 2002 4:11 pm
 Location: Wroclaw, Poland
 Contact:
topics are divided into pages ... on top of table with list of them you see some numbers like 1,2,3 .... and so on ....
Try to click on it and you got next page of forum for such vlume
Bet regards
DM
Try to click on it and you got next page of forum for such vlume
Bet regards
DM
If you really want to get Accepted, try to think about possible, and after that  about impossible ... and you'll get, what you want ....
Born from ashes  restarting counter of problems (800+ solved problems)
Born from ashes  restarting counter of problems (800+ solved problems)
I've found it!
Sorry, I've found it now!!!
My search was using the board search feature, on 10213, and it did not return that topic...
Looking page by page, I've found it, is there a bug in the search engine?
Again, sorry for my fault..
JP!
My search was using the board search feature, on 10213, and it did not return that topic...
Looking page by page, I've found it, is there a bug in the search engine?
Again, sorry for my fault..
JP!

 Guru
 Posts: 834
 Joined: Wed May 29, 2002 4:11 pm
 Location: Wroclaw, Poland
 Contact:

 New poster
 Posts: 35
 Joined: Sat Jan 05, 2002 2:00 am
 Contact:

 New poster
 Posts: 4
 Joined: Wed Oct 22, 2003 9:11 pm
10213 how to solve?!?
huh
for k points
is it the answer something like 2^k
can you suggest some recurrence relation
thanks!
nick
for k points
is it the answer something like 2^k
can you suggest some recurrence relation
thanks!
nick