The strange case of The Pigeon-hole Principle

November 10, 2012 7:04 AM

It's Saturday; why not think about the pigeonhole principle? Here are problems and more problems and what you might call a problem with the principle itself as it is often stated.
posted by Wolfdog (41 comments total)

Among the problem lists, I didn't see one of my very favorite problems, so here: Prove that every positive integer n has a positive multiple which is written with only 1's and 0's.

(For example, for n=3 there is 3*37=111; for n=4 there is 4*25=100; for n=7, there is 7*1443=10101; for n=23, there is 23*4787=110101; and so on.)
posted by Wolfdog at 7:10 AM on November 10, 2012 [11 favorites]

Describing the "covering checkerboard with opposite corners removed with dominos" problem as an application of the Pigeonhole is quite a stretch. You might even call it forcing a square pigeon into a round hole.
posted by escabeche at 7:30 AM on November 10, 2012 [5 favorites]

This sounds like it is related to the Pigeon-hole Principle- if someone more skilled with the maths can verify though:

For a given measured quantity, in a sample of five randomly selected members of a population greater than five, there is at least a 93.8% probability that the mean of the entire population will fall between the highest and lowest members of the sample. (From D.Hubbard- How to Measure Anything)
posted by Phyllis Harmonic at 7:57 AM on November 10, 2012

Oh god, memories of discrete math coming back to haunt me...
posted by squorch at 8:10 AM on November 10, 2012

If you think this is neat, you might be interested in the "Strong Law of Small Numbers" which is related. I'd provide links but I'm unable to decide which ones.
posted by wobh at 8:13 AM on November 10, 2012 [1 favorite]

For a given measured quantity, in a sample of five randomly selected members of a population greater than five, there is at least a 93.8% probability that the mean of the entire population will fall between the highest and lowest members of the sample.

This had better not follow from the Pigeonhole Principle, because it's false. Suppose there are a million people with a salary of $50K and one person with a salary of $1m. The mean salary is a little over $50K. But if you sample 5 people at random, the probability is very high that all five of them will have salary exactly $50K, so the mean of the population won't be between the highest and lowest members of the sample.

The source you quote is presumably making some assumptions on the distribution of the measured quantity.
posted by escabeche at 8:20 AM on November 10, 2012

Phyllis, that is not related. Also, the author is making a big assumption in there: that the population median and mean are the same. If this is true, then the probability of a given datum being on one side or the other of the mean is 0.5. So, the probability of all 5 being on one side is 0.5^5. Since there are two sides, the probability of the mean not being in the interval formed by the samples is 2*0.5^5, so the probability that it is in is 1-2*0.5^2=0.9375.
posted by cap11235 at 8:24 AM on November 10, 2012

But wait, if the median and the mean are the same, isn't the probabilty exactly 15/16? Why would he say "at least"?
posted by escabeche at 8:31 AM on November 10, 2012

What I've always wondered is what kind of messed up person stuffs pigeons into holes? Poor birdies.
posted by Zalzidrax at 8:38 AM on November 10, 2012 [2 favorites]

Hubbard's actual "Rule of Five" is

There is a 93% chance that the median of a population is between the smallest and largest values in any random sample of five from that population.

Not mean, not "at least 93%". (Actually the real probability is 93.75%, as cap11235 points out.)

So escabeche and cap11235's issues with the misstated rule are correct but don't apply to the actual one.

Now let's get back to the pigeonhole principle!
posted by dfan at 8:39 AM on November 10, 2012 [1 favorite]

Yes, why does no-one ever think of the poor pigeons?

Still at least we've established that 5 is not a great sample size.
posted by philipy at 8:42 AM on November 10, 2012 [1 favorite]

What I've always wondered is what kind of messed up person stuffs pigeons into holes?

In Hungarian, it's the matchbox principle, if that makes you feel any better about it. Had the nomenclature been decided in the internet age, I'm certain it would be universally known as the catbox principle.
posted by Wolfdog at 8:48 AM on November 10, 2012 [2 favorites]

Hilbert totally demolished this concept.
posted by charlie don't surf at 8:50 AM on November 10, 2012

Not really! I have uncountably many guests who want to visit Hilbert's hotel. (IF HE CAN HAVE AN INFINITE HOTEL, I CAN HAVE UNCOUNTABLY MANY GUESTS.) There will be multiple occupancies.
posted by Wolfdog at 8:52 AM on November 10, 2012 [1 favorite]

I demand uncountably many Schrodinger's Catboxes.
posted by philipy at 9:10 AM on November 10, 2012

I have uncountably many guests who want to visit Hilbert's hotel.

Yeah, Cantor took care of that one.
posted by charlie don't surf at 9:22 AM on November 10, 2012

Thanks for clarifying my earlier post, guys. I confess to relying on recall- which is getting more risky all the time, dammit.
posted by Phyllis Harmonic at 9:59 AM on November 10, 2012 [1 favorite]

My favorite variation: http://en.wikipedia.org/wiki/The_Library_of_Babel
posted by cschneid at 10:03 AM on November 10, 2012

Further links on that page led me to this wonderfully named theorem. I propose that it be renamed the Gervais Theorem.
posted by irrelephant at 10:24 AM on November 10, 2012

There's also this handy algorithm. Might come in useful when you're combing hairy balls.
posted by iotic at 11:34 AM on November 10, 2012 [1 favorite]

What I've always wondered is what kind of messed up person stuffs pigeons into holes?

Originally referred to the nesting boxes in dovecotes— pigeons actually like to have a nook to nest in. Desk cubbyholes reminded people of dovecots (or possibly reminded people of ossuaries, which reminded people of dovecotes) and the mathematical idea reminded people of desk cubbyholes.
posted by hattifattener at 12:00 PM on November 10, 2012

Years ago, in Siena, I saw a vivid demonstration of the Principle.
posted by j.edwards at 1:44 PM on November 10, 2012

I use it to explain why polygamy is a terrible idea for most men.
posted by Brian B. at 3:03 PM on November 10, 2012 [1 favorite]

OK, I've been working on Wolfdog's problem off and on for the better part of the day, and I think I've got it. If someone could check my proof that would be cool. I haven't done a rigorous proof in a while.

POSSIBLE SPOILERS IF I'M RIGHT ——————————————————
Ok, so we're given n. Any other number m, when divided by n, must have a remainder that is between 0 and n - 1 inclusive. (In more concise but also more jargon-y terms, consider m mod n.) These remainders will be our pigeonholes.

For the pigeons, consider the first n terms of the sequence 1, 11, 111, 1111, ...
Because there are n of them and only n - 1 possible remainders, the pigeonhole principle says two of them must have the same remainder when divided by n.

If you take these two terms and subtract the smaller from the larger, you have a number whose digits are some number of 1s followed by some number of 0s, and it is divisible by n. QED.

That last assertion—that the difference of two numbers with the same remainder mod n is divisible by n—is a pretty basic fact of number theory but here is a proof if you need it: let the two numbers be a and b and assume a > b. Then—this is basically the definition of a remainder—for some integers q₁ > q₂,
a = q₁n + r and b = q₂n + r.
So a - b = q₁n + r - (q₂n + r) = (q₁ - q₂)n
which proves it's divisible by n.
END POSSIBLE SPOILERS ———————————————————————

If I'm right in thinking that proof works, I can see why you like that problem so much, Wolfdog. I have to say I was extraordinarily pleased with myself when I solved it, and it's a nice, elegant little solution and use of the pigeonhole principle.
posted by valrus at 4:55 PM on November 10, 2012 [3 favorites]

There are n possible remainders (you said 0 to n-1 inclusive), but I guess all you have to do is take the first n+1 terms instead. The rest seems reasonable to me at first glance.

I guess that proves an even stronger result, in that the multiple of n is some number of 1s followed by some number of 0s, not just some combination of 1s and 0s.
posted by dfan at 5:08 PM on November 10, 2012 [1 favorite]

Oh, you're right. Oops. I think I've been prone to off-by-one errors all my life. :/
posted by valrus at 5:13 PM on November 10, 2012

Impressive, valrus. I really like your proof. I had been thinking of it off and on for most of the day also!
posted by King Bee at 5:44 PM on November 10, 2012

I’m not much of a mather, but none of the examples or statements seemed surprising or unintuitive. Were they supposed to be, or am I missing the point?
posted by bongo_x at 7:26 PM on November 10, 2012

dfan: it occurs to me that the result could be made even stronger: there are an infinite number of such multiples. I guess I don't know if there's a formulation of the pigeonhole principle that applies if you have infinite pigeons, but it seems obvious that if there are finitely many pigeonholes, one's got to have infinitely many pigeons in it.
posted by valrus at 10:57 PM on November 10, 2012

If you have infinite pigeons there's going to be a lot of poop. I hope you haven't parked your car anywhere nearby.
posted by iotic at 12:27 AM on November 11, 2012

dfan: it occurs to me that the result could be made even stronger: there are an infinite number of such multiples.

True, but that was clear already; once you get your first one, you can add as many zeroes as you want on the end and it'll still be a multiple of the original number.
posted by dfan at 5:58 AM on November 11, 2012

derp
posted by valrus at 7:26 AM on November 11, 2012

Nice work, valrus!
posted by the quidnunc kid at 9:03 AM on November 11, 2012

Nice work indeed! Also, you're right that you only need to look at the first n terms of your sequence. If any of those is zero (mod n), then it's your solution. Otherwise, there's a pair with the same nonzero remainder mod n. So you weren't off by one after all! And if you wanted to strengthen the result just a little bit, you could add "Furthermore, if n is relatively prime to 10, then n has a multiple with only 1's."

Tricky as the problem is, it is much harder when it doesn't come in a thread about the pigeonhole principle.
posted by Wolfdog at 10:34 AM on November 11, 2012

I solved it when I had to solve a different problem: that any integer prime to 10 has a multiple, all of whose digits are 7. And, yes, I did it that same way.
posted by Obscure Reference at 11:55 AM on November 11, 2012

Now, can we find a method for finding the lowest such solution? I.e. the lowest multiple of any n that consists of only zeros and ones.
posted by iotic at 12:08 PM on November 11, 2012

I was really hoping someone would say: "write n in binary, then QED".
posted by the quidnunc kid at 1:53 PM on November 11, 2012 [1 favorite]

Brute force can find the lowest, now that we know that algorithm will eventually terminate. The question is whether we can find a method with worst-case run time better than O(n).
posted by Nioate at 6:20 PM on November 11, 2012

Now that I have my undergrad set theory book in front of me, I can confidently state the following infinite version of the pigeonhole principle:

Let κ ≤ λ and let μ be the largest number such that λ > κ × μ. Then if A is a set of size λ and P is a partition of A into κ subsets, at least one subset in the partition has size greater than μ.

So, for example, if you divide 8 things up into three piles, at least one of the piles has at least 3 things in it. But what's great is that this works even when both κ and λ are infinite cardinals, as well. And since ℵ_α×ℵ_β = ℵ_β whenever α ≤ β, this means that if you divide an uncountable set into countably many piles, at least one of the piles has uncountably many things in it.
posted by Elementary Penguin at 2:45 PM on November 13, 2012

Argh. Let μ be the smallest number such that λ ≤ κ × μ … has size greater than or equal to μ.
posted by Elementary Penguin at 4:19 PM on November 13, 2012

A fun generalization of valrus' proof would seem to be that you can take any n,m whatever, and there is some multiple of m which consists of repetitions of the digit string of n followed by a bunch of zeroes.

For example you could take your phone number, and for any n, there is some multiple of n that is your phone number repeated umpteen times and then lots of zeroes.
posted by philipy at 9:36 AM on November 14, 2012 [1 favorite]