[superprismatic]

If we place N points, no three of which are

collinear, in the box {(x,y)|0≤x≤1 & 0≤y≤1},

then we connect every pair of these points

with straight line segments, there may be

some segments which cross other segments.

Let F(N) be the minimum number of crossings

for N such points. It's pretty easy to see

that F(N)=0 for 2≤N≤4, and F(5)=1.

Find F(N) for N=6,7,8,9, and 10.

By "crossing" I mean that two line

segments have precisely one point in

common which is not an endpoint of

both segments. The problem, then, has

to do with counting the number of

distinct such points.

[Guest]

If we place N points, no three of which are

collinear, in the box {(x,y)|0≤x≤1 & 0≤y≤1},

then we connect every pair of these points

with straight line segments, there may be

some segments which cross other segments.

Let F(N) be the minimum number of crossings

for N such points. It's pretty easy to see

that F(N)=0 for 2≤N≤4, and F(5)=1.

Find F(N) for N=6,7,8,9, and 10.

By "crossing" I mean that two line

segments have precisely one point in

common which is not an endpoint of

both segments. The problem, then, has

to do with counting the number of

distinct such points.

Surely, F(4)=1 and not 0 as mentioned. The two diagonals in a square will cross. Or the two lines from opposite points of any four sided shape.

Maybe I am not understanding the puzzle correctly. Or am I?

[Guest]

F(4) can be zero if three points form a triangle and the fourth is any point inside this triangle

[Guest]

For 6 points the minimum crossings would be 3. You can have it by drawing an equilateral tirangle inside another equilateral triangle with the same centroid

[Molly Mae]

6.

Adding an slightly off-centre point to Deegee's model for F(6). Just avoid making the centre point and the the top point of each triangle colinear.

Edited August 31, 2010 by Molly Mae

[Guest]

What is sought is known as the Rectilinear Crossing Number for a straight line drawing. Beginning at n=3, the terms for the sequence of F(n) are:

0, 0, 1, 3, 9, 19, 36, 62, 102, 153, 229, 324, 447, 603, 798, 1029, 1318, ...

F(6) = 3

F(7) = 9

F(8) = 19

F(9) = 36

F(10) = 62