2
$\begingroup$

A set of $17$ points is chosen on the circumference of a circle. Find the maximum number of segments which can be drawn connecting pairs of points such that each segment intersects all others inside,not on, the circle.

Giving away one constraint of the problem I have $\dbinom {17}{2} $ segments which can be drawn between any two pair of points.

Now the segments which intersects all others on the circle are the ones which are found when we take a point on the circumference and calculate how many segments can be drawn from this point to any other point on the circumference,hence $17-1$ segments.

This happens for every point on the circumference,so I have $\cfrac {\dbinom {17}{2}}{16} $ segments which satisfy the constraint.

I haven't been able to find the solution of this problem on the Internet. Can someone check my work ?

Edit: I've caught up the mistake it should have been $\cfrac {\dbinom {17}{2}}{17} $ since given a point on the circumference I am forming $17$ pairs.

$\endgroup$
  • $\begingroup$ $\frac{\binom{17}{2}}{16}$ is not a whole number... $\endgroup$ – Michael Biro Nov 24 '15 at 14:53
  • $\begingroup$ I can't understand what's wrong.The arguments seems to be correct .Can you help ? $\endgroup$ – Mr. Y Nov 24 '15 at 15:01
4
$\begingroup$

Consider the following: you have 17 possible endpoints to choose from in creating segments. If you use the same endpoint for two segments, those two segments will not intersect inside the circle: enter image description here

Hence, each of your 17 endpoints can be used at most once, which means at most 8 segments can be drawn. In fact, you can also show that at least 8 segments can be drawn, by choosing pairs of endpoints that are roughly opposite (formally, if you number the endpoints going around the circle from $1$ to $17$, choose the segments $(1, 9), (2, 10), \ldots$).

enter image description here

Thus, you can draw 8 segments.

$\endgroup$
3
$\begingroup$

Yes, 8 seems correct. As you observed, if there are 9 segments, then two of them will share a end-point and cannot intersect inside the circle.

Eight is possible: label them clockwise as $1,2,\ldots,17$ and join $i$ to $i+8$.

$\endgroup$
1
$\begingroup$

I don't think you are reading the problem correctly. If we number the points $1$ through $17$ around the circle and draw the line from $1$ to $9$, it will not intersect the line from $2$ to $8$ inside the circle. For the second line you need one endpoint in $[2,8]$ and one in $[10,16]$. If you keep going you can get $8$

$\endgroup$

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.