How many sides does the n-gon have?

[maverick280857]

Here's a problem my friend gave me:

The number of points of intersection of diagonals of a n-gon is 70. If no three diagonals are concurrent, find the number of sides of the n-gon.

I believe the answer is 20.

I tried to work out for small values of n to get a feel but that didn't do much good. As n increases so does the number of intersection points but how to set up an expression relating this number to n? Suggestions are appreciated.

Thanks
Vivek

 

[AKG]

Assume we have 11 dots, arranged on the face of a clock (leaving a gap for "12 o'clock"). Create all the diagonals connecting these dots, and let the number of intersections be N(11). Now, what happens when you add a dot at 12 o'clock? Now, the line connecting 1 o'clock and 11 o'clock can be crossed 9 times by diagonals starting at 12. This is because there are 9 points under that diagonal (by "under a diagonal", I mean that if you were to connect 12 o'clock to a point under a diagonal, then the line joining 12 and that point would have to cross that diagonal). How many diagonals have 9 points under them? Just the one joining 1 and 11.

Consider the diagonal joining 5 and 7 o'clock. This diagonal has only one point under it, namely 6, so in crossing this diagonal, a line from 12 will only make 1 intersection. How many such diagonals are there? 9:

From 1 to 3 (with 2 underneath)
From 2 to 4 (with 3 underneath)
.
.
.
From 9 to 11 (with 10 underneath)

You can easily show that the number of diagonals with k points underneath is 10 - k. If you want to check this for yourself, choose a k, then let the first diagonal you consider be the one from 1 o'clock to the one at k+1 o'clock, and then just go clockwise around (so consider the diagonal from 2 o'clock to k+2 o'clock next) and you'll see that there are 10 - k such diagonals, and that these diagonals are all of them that have k underneath.

So, by adding a dot at 12 o'clock, how many intersections do you add?

$$\sum _{j = 1} ^{12 - 3} j(12 - 2 - j)$$

In general, let's say you're adding the p'th dot, how many intersections do you add?

$$\sum _{j = 1} ^{p - 3} j(p - 2 - j)$$

You can see why we go up to p-3. Imagine we're in the case with 12 again. How could we make a diagonal such that all the lines coming from 12 o'clock crossed it 12 times? Or even 11 times? Or even 10 times? Those are all impossible cases, and you'll see that p - 3 is, in general, the "largest" possible case. Why do we have "j(p - 2 - j)" in the sum? Well "j" is the number of intersections, and (p - 2 - j) is the number of ways to get these intersections. You should be able to figure out why this is. What does this give us?:

$$N(p) = N(p - 1) + \sum _{j = 1} ^{p - 3} j(p - 2 - j) = N(p - 1) + {{p - 1}\choose 3}$$

With N(0) = ... = N(3) = 0. You can expand this expression for N(p) in terms of N(q) + (some stuff) for lower and lower values of q until you hit q = 3, i.e. you can find a closed form solution for this recurrence relation. You'll get:

$$N(p) = \sum _{i = 3} ^{p - 1} {{i}\choose 3}$$

If you want, you can try writing it without the sum, i.e. just a closed form expression in terms of p so that it might be easier to solve for N(p) = 70, but you can just try N(p) for different values of p and find the right one. Note that your guess of 20 is way too big.

Make the diagram for p = 3, 4, 5, 6, and see how rapidly N(p) increases.

 

[maverick280857]

Thanks for the detailed reply AKG (and sorry for my late reply)...I am going to take a printout of this and work it out.

Thanks and cheers
vivek