1
$\begingroup$

I was given the following problem: "Using one straight line we can divide a crescent (a.k.a. lune) into a maximum of 3 regions. Using two straight lines we can divide a crescent into a maximum of 6 regions. Find a formula giving the maximum number of regions one can create when n straight lines are used.You must provide a proof that your formula is correct."

I've got no idea where to start this problem, I tried drawing the 3rd, 4th, and 5th lines, but so many small regions are created I don't know if I counted right

1->3

2->6

3->10

4->15

5->21

Could someone at least point me in the right direction to start this problem

Picture given with problem

$\endgroup$
  • $\begingroup$ You can use OEIS to turn sequences into formulas, but that doesn't verify your sequence is correct, much less proove that it is. $\endgroup$ – MvG Jan 17 '14 at 20:39
1
$\begingroup$

In order to maximize the number of regions, it seems you want to make sure that

  1. every line intersects the inner boundary of the crescent, either in two distinct points or in a double point where it is a tangent like in your figure and
  2. every line intersects every other line in the interior of the crescent.

Depending on how rigorous your proof has to be, you might have to elaborate on this point.

So you could choose $n$ points on the interior of the crescent, and draw a tangent at each. Then you consider the whole thing as a graph in terms of its Euler characteristic formula:

  • Every straight line intersects all other lines and also touches the inner boundary. So every one of the $n$ lines contributes $n+1$ straight line segments as edges of the graph. Furthermore, the inner arc is intersected once by every line, so it is split into $n+1$ curved edges. The outer arc is intersected twice, resulting in $2n+1$ curved edges. So the total number of edges is

    $$E=n(n+1)+(n+1)+(2n+1)=n^2+4n+2$$

  • Every point of intersection between two lines is a vertex, amounting to $\binom{n}{2}=\frac{n(n-1)}2$ vertices inside the crescent. Then there are $n$ points where the lines intersect the inner arc, and $2n$ where they intersect the outer. The tips where inner and outer arc meet contribute two more vertices. So the total number is

    $$V=\binom n2+n+2n+2=\frac{n^2+5n+4}{2}=\frac{(n+1)(n+4)}{2}$$

  • From these two you can deduce the number of faces, not counting the one outside the crescent, as

    $$F=\chi+E-V=1+E-V=\frac{n^2+3n+2}{2}=\frac{(n+1)(n+2)}{2}$$

    This is because topologically your crescent is a disk, so it has Euler characteristic $\chi=1$.

Except for an offset of one in the indices (i.e. the value of $n$), these are exactly the triangular numbers. They do confirm the numbers you gave in your question, so you did count right.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ This is a very symmetrical example of what looks to be the maximum. +1. (I didn't notice before that each inner tangency in effect makes another region.) $\endgroup$ – coffeemath Jan 18 '14 at 3:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.