Home > Problem of the Week > Archive List > Detail

 << Prev 11/14/2010 Next >>

This week's problem was found via a daily internet feed that suggests new problems to play with in my spare time. It proved interesting, so I share it with some slight variations and significant extensions.

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

Find a set of three points in the box such that, if every point is connected to every other point by a straight line segment, no two line segments intersect.

Find a set of four such points.

Now, can you find a set of five or more such points? Explain why or why not.

Note for the Clever Minds: The points have to be contained in the "box", which means you are restricted to two-dimensions.

BUT if you are allowed to place points in a 3-dimensional box, how many points can you place before running into trouble...if at all? And, what about a n-dimensional box?

Source: Puzzles and Riddles, August 28, 2010

Hint: For the three-point case, try the points (0,0), (0.5,1), and (1,0). The subsequent line segments form a triangle, and thus, no two of the "sides" intersect except at the vertices.

When the problem was posed, one submitted solution was: (0,0), (1,0), (0,1), (.5,.5), (1,1). Why is this wrong?

Solution Commentary: You should be able to adjust the solution for the three-point case to solve the four-point case. And in doing so (i.e. reflecting on your process), you will gain important information about the five-point case.

"MAgician" submitted this response on-line as follows...do you agree it is a solution?

I don't think it's possible. Consider the following: If three such points are created, they will always form a triangle. You then have two possible places to put the fourth point: inside the triangle or outside the triangle (not all points outside the triangle will work, but I'm assuming you choose one that does)...this leaves us with three cases for the remaining two points: one inside and one outside; two inside; or two outside. Now consider each of those cases:
• one inside and one outside: no matter what, the line between those two points will cross one of the sides of the original triangle>/li>
• two inside: the first one inside divides the triangle into three triangles, leaving you with three places to put the last point. However, whichever triangle you put it in, the line between the point that you just placed and the point that is not a vertex of that triangle will cross one of the sides of the triangle. (it essentially reduces to one inside and one outside)
• two outside: because order of placement is irrelevant, the first one outside could just as easily be a vertex of the original triangle and one of the points that was a vertex of the original triangle is then a point inside the triangle dividing it into three triangles. Thus, this case reduces itself to either of the other two cases depending on your placement of the second point.
Therefore, there is no set of five such points. QED