The pigeonhole principle has many generalizations. The pigeonhole principle made what seemed like a slippery argument airtight. But the diameter of the smaller square is Sqrt/2, so these two points must be closer than 3/4, as claimed. So, if I divide up the square into 4 smaller squares by cutting through center, then by the pigeonhole principle, for any configuration of 5 points, one of these smaller squares must contain two points. (This proof shows that it does not even matter if the holes overlap so that a single pigeon occupies 2 holes.) It is easy to see why: otherwise, each hole as at most 1 pigeon and the total number of pigeons couldn't be more than 4. A basic version says that if (N+1) pigeons occupy N holes, then some hole must have at least 2 pigeons. Thus if 5 pigeons occupy 4 holes, then there must be some hole with at least 2 pigeons. The pigeonhole principle is one of the simplest but most useful ideas in mathematics, and can rescue us here. But what may be harder to show is that this is really the extreme case why can't any other configuration be more extreme? In this case adjacent points are exactly distance Sqrt/2 ~ 0.707 apart. If you play with this problem for a while, you'll realize quickly that the extreme case occurs when 4 points are at the corners of the square with a 5th point at the center. How about an easier question: can you show that if you place 5 points in a square of sidelength 1, some pair of them must be within distance 3/4 of each other? Here's a challenging problem with a surprisingly easy answer: can you show that for any 5 points placed on a sphere, some hemisphere must contain 4 of the points?
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |