Wednesday 30 January 2013

Distance between points inside a unit square




Distance between points inside a unit square

Great problem, can be reasoned with what is called Pigeonhole principle, shown below:
if n items are put into m pigeonholes with n > m, then at least one pigeonhole must contain more than one item.
All it says is this then: suppose I had 5 pigeons and 4 holes, if I have to put the pigeons in the holes there will always be at least one hole which will have more than 1 pigeon, simple right ?
pigeon-hole principle
Now, how do I use this reasoning to solve the problem, read on.
Take my unit square, and divide it into 4 squares (the holes), as shown below, each square is of size 1/2 x 1/2. Now select 5 points inside the unit square at random. Now, there will always be at least one hole (one of the four 1/2 x 1/2 squares) where at least 2 out of the 5 chosen points will lie, right. (the pigeon-hole principle). Let those points be D & E that lie within the same 1/2 x 1/2 square.
pigeon-holes inside a unit square
What would be the maximum distance between D & E, inside a 1/2 x 1/2 square - that would be the length of its diagonal right (see the picture again).
Length of diagonal of 1/2 x 1/2 square = √2 * (1/2) or 1/√2. And so we would say that there are going to be least two points out of the five whose distance will always be limited to (less than) 1 / √2

0 comments:

Post a Comment