Mathematics Problem Of the Week

Fall 2007

POW #4

Connect the Dots

Suppose that we have n points in the plane labeled 1, 2, ..., n such that no three points are collinear (on the same line).

Part A: What is the minimum number of straight lines needed to have a line going directly between each pair of points? Justify your answer.

Part B: What is the minimum number of triangles, drawn with vertexes at the points, in order to provide a path to get from any point to any other point? Ignore places the triangles might cross that aren’t in the point set, i.e. you can only go from one triangle to another at a vertex. Again, include a justification for your answer.

Due Friday, September 28^th at Noon.

Solutions should be submitted to Dr. R. Lock's mailbox in the Math/CS/Stat office or sent via e-mail to rlock@stlawu.edu.