10213 - How Many Pieces of Land ?

[chang]

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.

[Even]

5 16
6 31
7 57
8 99
9 163
10 256
2^31-1 886151993063477126682488902248300547

and use BIG NUM...
I got WA even use long double...

[chang]

Hey Even!

Thanks for ur reply.
Oh! my recurrence was wrong. But I can't detect how the recurrence can be built. Would u please inform how built up ur recurrence,Or is there any direct formula to solve this one?
Thanks in advance.

[..]

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 2002-01-20 07:55 ]</font>

[chang]

Hey ..

Would u pls tell how u derive that formula by induction procedure? I'm really so curious to know it. I've the idea of induction, but I can't find out the way of thinking.
Thanks in advance.

[..]

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(n-1), want to know P(n) by adding the n-th point

when the n-th point draw a line to the k-th point (1 <= k <= n-1)
on the LHS on k-th point, there is k-1 points between k-th and n-th point
on the RHS on k-th point, there is (n-1)-k+1 points between k-th and n-th point
the points in these 2 sets(LHS, RHS) are completely connected,
so there are (k-1)*(n-k) lines crossed by the newly drawn line,
creating (k-1)*(n-k)+1 new lands......

So, drawing lines from newly added n-th point to all n-1 old points,
will create

summation[(k-1)(j-k)+1] {k = 1..j (j = n-1)} new lands

let says the summation be F(j)

P(n)= P(n-1) + F(n-1)
= P(n-2) + F(n-2) + F(n-1)
.....
= P(0) + F(1) + F(2) + ....... + F(n-1)
= 1 + summation(F(i)) {i = 1..n-1}


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~

[zhangl]

answer=c(n,4)+c(n,2)+1

[jpfarias]

Hi all!

I was thinking in this problem and don't get the recurrence relation...

Can anyone help?

Thanks,

JP!

[Dmytro Chernysh]

Or yes... this one is very hard. I just can give an answer
answer = (n - 1) * n * (n * n - 5 * n + 18) / 24 + 1
please, take a look at the previous posts...

[jpfarias]

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?

[Dominik Michniewski]

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

[jpfarias]

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!

[Dominik Michniewski]

No problem. Life is sometimes hard

DM

[Alexander Denisjuk]

By the way, it is not very hard to obtain the formula. The easiest way is the following:

1. To beleive that the formula is polynomial.
2. To calculate the interpolation polynomail.

[chervensky]

huh
for k points
is it the answer something like 2^k
can you suggest some recurrence relation

thanks!

nick