Processing math: 5%

Tuesday, November 1, 2011

Monday, October 31st

Problem


A strip of width w is the set of all points which lie on, or between, two parallel lines distance w apart. Let S be a set of n \geq 3 points on the plane such that any three different points of S can be covered by a strip of width 1. Prove that S can be covered by a strip of width 2. 


Solution  


Since we have a finite set, there is a pair of points in S which are the furthest apart from each other. Then every point in S is in a strip  of width 1 with one of its sides being the line passing through the maximal pair. Hence S lies inside the union of two such possible strips. 

No comments:

Post a Comment