A Bird in the Hand is Worth a Pigeon-hole Principle

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 invovling 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.

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... 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"

Two Problems

OK, take off your political blinders, whether you are conservative or liberal, and read this comparison like a mathematician/statistician. It is a comment about large multi-national companies and their relation with smaller nation-states. Be warned, there is a major flaw (and many minor ones) in this argument… find it :
”In Nigeria, a relatively economically strong country, the GDP is $99 billion. The net worth of Exxon is $119 billion. ‘When multi-nationals have a net worth higher than the GDP of the country in which they operate, what kind of power relationship are we talking about?’ asks Laura Morosini. [Source: ‘Impunity for Multinationals’, ATTAC, 11 Sept 2002”

Ok, little things that niggle (yes, that IS a word) at me; Exxon’s net worth includes the value of off-shore oil rigs in the Gulf of Mexico and office buildings in downtown Houston (or wherever). It would not be practical to think they could use all of that value to bring to bear in a competitive situations…. And GDP is the value of goods and services sold in the country…. You sell me a watermelon for $3.00 and it goes into the GDP, you spend that $3.00 for (part of ) the payment on a car, the $3.00 counts again…. so Nigeria couldn’t use all that in a conflict with Exxon (footnote, when the Exxon Valdez went aground and spread crude oil over large parts of Alaska’s waterfront, the GDP of Alaska went up… all those people cleaning up sludge, even if they were volunteers were eating food, renting motel rooms… driving up the GDP… see, disasters are GOOD for you)….. but neither of those are the BIG one…. Think… what is being compared??…

OK, here is a similar comparison, I have $1000 in my bank account (not really, I’m practically broke, but hypothetically) and you make $8.50 an hour at McDonalds, so I have an economic advantage in trade with you…… see it, one is a rate and one is a fixed value. In the Exxon/Nigeria situation, the GDP is measured each year…just by custom, and the value of Exxon is just Dollars, a fixed value. What if it was the custom to measure GDP on a ten year basis. Now we would have a GDP of $990 billion for Nigeria, and poor old Exxon looks like a chump with only $119 Billion. The idea in Physics and math class was called units analysis. If you needed newtons, which is Kg meters/sec², then you needed to multiply mass times distance and divide by the square of time.. and with comparisons, they don’t make sense if you are not comparing the same thing…. My car gets 26 miles to the gallon and the Eiffel Tower is about 324 meters high??? Yeah… and so what? The trouble is, when people like Ms. Morosini (a wonderful person I’m sure) make comparisons like this, you have to do more than just nod and smile…. THINK, ask questions…..

OK, second problem… What is the least likely group to be hurt by the increased gasoline pump prices? Did you say “People who don’t own cars”? You would think that, but I just read in an AARP article (OK, I’m old, put your big girl panties on and deal with it) that gas prices are causing a big drop in volunteers to deliver meals-on-wheels programs to shut-ins. Without sufficient manpower, many have resorted to delivering one hot meal and several prepared frozen meals so that they don’t come as often. In addition, as the economy goes south, the people who donated money and food for the program and reducing their contribution. Ok, children; Ignore the signs…DO feed the old people. One of those fundamental rules of Economics is called the Law of Unexpected Consequences. It’s a good one to keep in mind, especially if you think you have the solution to any economic problem.