Sometimes problems that seem very hard, can be very easy if they are viewed in the right way, and one of those easy ways to make some hard problems manageable is the Pigeon-Hole Principle. Over the last few weeks seems like lots of problems involving this idea have shown up, so I thought I would bring it to you.
The basic idea is so easy any sixth grader would agree; if you have two boxes, and you are going to put three balls in the boxes, then at least one box will get more than one ball..... "well, Duh!" they answer... and yet... it seems easier to apply than it might be. Now that you know the secret, try these two problems. I'll post the answer down lower on the page where you must not look until you take a few minutes to ponder the problems.
Here is the first from a recent blog I read: "39 people are attending a large, formal dinner, which must of course occur at a single, circular table. The guests, after milling about for a while, sit down to eat. It is then pointed out to them that there are name cards labeling assigned seats, and not a single one has sat in the seat assigned to them. Prove that there is some way to rotate the table so that at least two people are in the correct seats."
This one seems tougher, but really isn't, it just requires a different way of thinking. "Suppose you pick six unique integers from 1 to 1000. Prove that at least two of them must have a difference that is a multiple of five.
Before I give you the answers, I will throw in a little cultural information that may amuse and entertain you. The same axiom is often named in honor of Dirichlet who used it in solving Pell's equation. In a discussion on a history group a few years ago Julio Cabillon added that there are a variety of names in different countries for the idea. His list included "le principe des tiroirs de Dirichlet", French for the principle of the drawers of Dirichlet, and the Portuguese "principio da casa dos pombos" for the house of pigeons principle and "das gavetas de Dirichlet" for the drawers of Dirichlet. It also is sometimes simply called Dirichlet's principle and most simply of all, the box principle. Jozef Przytycki wrote me to add, "In Polish we use also:"the principle of the drawers of Dirichlet" that is 'Zasada szufladkowa Dirichleta' ". You just can't have TOO many names for a really useful idea.
Ok, The Proofs... for number one... Suppose you handed each person a number that was how many seats they needed to move to the right to find their assigned seat. Since no one is at the right seat, the number can not be zero or thirty-nine. SO each of the people has a number between 1 and 38...wait, there are 39 people...two of them (at least) must be the same distance away from their assigned seats.... admit it…..that’s pretty cool. (I have a slight question about whether this actually proves the solution of "rotating the table" to put two in their correct seats. Suppose we know that persons A and B are in each others seats and 5 seats apart. Rotating the table five seats in either direction would only put one of them in their correct seat. Maybe all we proved is that there are , at least, two people who are the same distance from their seat. If we had specified how far away in a clockwise direction they are from their correct seat, we would have a solution to the rotation of the table problem.)
For number two it is sort of the same idea, but you have to think about how much each number would have for a remainder if you divided them by five. The only possible choices are 0, 1, 2, 3, or 4... , five different remainders, but there are six numbers, so two of them have the same remainder...and two numbers that have the same remainder on division by five, are a multiple of five apart.... think of 1,6, 11, etc for remainders of one. If you want to read more about how remainders can play a part in solving problems, see my blog on "casting out sevens" (And other primes)
No comments:
Post a Comment