Interview Question

Quantitative Trader Interview

-New York, NY

Jane Street

N points lie on a circle. You draw lines connecting all the points to each other. These lines divide up the circle into a number of regions. How many regions is this? Assume that the points are scattered in such a way as to give the maximum number of regions for that N.

Answer

Interview Answers

14 Answers

7

it is "Moser's circle problem" 1+nC2+nC4

hi on

5

This is a famous example in mathematics; it's often used as a warning against naive generalization. Here are the answers for the first six natural numbers: (# points) : (# regions) 1 : 1 2 : 2 3 : 4 4 : 8 5 : 16 6 : 31 Yes, 31. You can see, e.g., Conway and Guy's "The Book of Numbers" for an account of this.

All of these are wrong. on

0

Err, 2*n-1+summation(n-1C->n-1)

Matt on

1

Hi, I also get Dimtar's formula, you may use the recursion method to do it, which takes some time. Is there any easy way to get this one? Btw, when there are 4 dots on a circle, I think it shoud still give 8 regions. I think 11 is the answer to another problem. If you make n cuts on a circle, the max shares you can create.

Chinshin on

2

I don't think that is correct. I can't see a way that, while obeying these rules, you can have 11 sections for 4 points. Perhaps the formula 2^(N-1)?

Anonymous on

2

i got 2^(N-1) as well

Anonymous on

0

1 2 4 8 16 31 57 1 2 4 8 15 26 1 2 4 7 11 1 2 3 4 1 1 1 0 0

AL on

0

mingda is correct

AL on

0

srsly? draw 4 lines yourself and you can easily find its 11

for those who think f(4)=8 on

5

1 dot - 1 region 2 dots - 2 regions 3 dots - 4 regions 4 dots - 8 regions 2^(N-1), N greater than or equal to 1

mike on

0

The unanswered question (and the reasoning behind the combinations thing) is whether two adjacent regions may have the line that divides them ignored for counting up a them both together as a new region. Dimitar's way assumes you may erase a line and Mike's way does not. However, for Dimitar's way, I think the combinations do not just stop at the nC4 + nC2, but really keep going up to n (and Dimitar just stopped at ~6 when he was testing the base cases). Mike's way assumes each region cannot be made up of sub regions, which I feel is the more correct answer, since it gives a scalable answer without summation/set notation, though you should ask the interviewer which he'd prefer. Let's take the 3 dot example: Mike's thinking: =There's the middle triangle and the 3 arc regions, so 4 Dimitar's thinking: =Mike's + triangle + 1,2,3 regions =4 + 3C1 + 3C2 + 3C3 =4 + 3 + 3 + 1 = 11 which really seems to break down into: 2^n-1+summation(nC1->n). I dislike Dimitar's way, because it invariably includes the entire circle as a "region" that has been created, which seems to go against the spirit of the problem.

Matt on

0

The last answer should be 1+(n-1)*n*(n^2-5n+18)/24. At first I thought it's 2^(n-1), because for the first 5 terms it's really the same, but when n=6, it should be 31. Solution: I use recursion. Assume the number of regions for n points is f(n). If we add a new point, we can count how many new regions are created. 1. outside the polygon of original n points, create n new regions. 2. inside the polygon, once the line between the new point and original point cuts the original line, there will be one more region. Label the original points clockwise as 1 2 3 ... n, and the line of the new point with point i will cut (i-1)(n-i) lines. This number is the number of points before the points i times the number of points after the point i. Then how to calculate the sum of (i-1)*(n-i), i.e., sum(k)*n + sum(k*(k+1)). The first term is easy. The second term in fact is a question in the book Heard On the Street. First we guess it's k(k+1)(k+2)/3, and then use mathematical induction to prove it in an easy way. After all, I get f(n+1) = f(n) + n + n*(n-1)*(n-2)/6. And then use recursion and formula for sum(k^3), sum(k^2), sum(k) to get the last answer.

Mingda on

2

I don't think the above answer is right.What happens if N is less than 4? Even if N is at least four, it still doesn't work For example, take the case when 4 lines are drawn, you can make 11 regions, but Dimitar's formula gives 4c4+4c2+1=8 The way you do it, is you start out with 1 region with 0 lines. Then you draw 1 line to get 2 regions. When the maximum number of regions is created, each new line will cross every previous line and will create a new region each time it crosses line. It also creates a new region just by being created. So the 2nd line makes 2 new regions, the third line makes 3 new regions, the fourth line makes 4 new regions etc. So the answer is the sum of the first N natural numbers +1. In general this is the formula N(N+1)/2+1

Anonymous on

4

n choose 4 + n choose 2 + 1

Dimitar on

One or more comments have been removed.
Please see our Community Guidelines or Terms of Service for more information.

Add Answers or Comments

To comment on this, Sign In or Sign Up.