pigeonhole principle

A basic principle of discrete math that is used quite often in theoretical computer science. This is one of those things where you think to yourself, "Why did anyone bother to right this down in a book?"

The Pigeon-hole Principle If k + 1 or more objects are placed into k boxes, then there is at least one box containing two or more of the objects. -- Rosen, Kenneth H.; Discrete Mathematics and its Applications, Third Edition

This principle was first stated by Dirichlet in 1834 and has important applications in number theory.

If m pigeons are put into m pigeonholes, there is an empty hole if and only if there's a hole with more than one pigeon.

It is also known as the Dirichlet's Box Principle, which reads:

If n>m pigeons are put into m pigeonholes, there's a hole with more than one pigeon.

Here's a simple application: if we have 37 students in our classroom, then at least 4 students must have their birthdays in the same month. (The pigeonholes are the months, so n = 12; clearly 37 = 12·3 + 1 so r = 3.)

A similar principle to the Pigeonhole Principle is the Fubini Principle:

If the average number of envelopes per pigeonhole is a, then some pigeonhole will have at least a envelopes. Similarly, there must be a pigeonhole with at most a envelopes.

The concept of the pigeonhole principle in simple noding terms:

If there are A nodes and B writeups that exist within the A nodes, where A>0, B>0, and A<B, then at least one node contains more than one writeup.

Suppose you have 51 nodes, and those nodes have id numbers between 100000 and 100099 inclusive. The pigeonhole principle can prove that at least two of your nodes must have id numbers that are consecutive integers (without having to spam Everything with a bunch of useless nodes).

For computer science, there seems to be a huge loophole in the Pigeonhole Principle, if it would be used to limit the number of possible data or algorithm entities to the highest binary integer that can be stored in the memory.

That number would have to be multiplied by various dimensions such as the number of possible data formats, programming languages, virtual machines, program entry points, and CPU register states.

That number would have to be multiplied by the as yet uncomputed number of similar non-copies of any entity and the number of possible unique original works to which those non-copies seem similar. A similar non-copy cannot exceed a difference of 50% unidentical bits, nor can a non-copy that is similar to a different original. A thought experiment would be if everyone in the world had gone to a concert and recorded a song with an MP3 recorder, it is virtually impossible for any two people to have created the same exact MP3 file. The limit of 50% maximum difference is based on the obvious idea of producing a perfect non-copy of an original by flipping every single bit, which would result in the equivalent of a photo negative.

I can demonstrate the creation of a file which contains one integer which can be simultaneously viewed as a digital photograph (or contrived likeness in art) and also as a song and also as a document of meaningful text, and also an executable program occupying the same space, and have done such things.

Before I was a teenager, I wrote a 26 byte program that outputs information which is interesting as raw bitmapped video and as musical sound, which goes on so long without repeating that it cannot be recorded on a single magnetic media device. Since then I have written hundreds of such programs, and even fixed them in tangible hardware. My primary example is a fast binary counter which outputs the equivalent of a binary Champernowne's Constant as a serial bitstream, and another which instantly retrieves any selected bit (or digit in other bases) according to an index value representing how many digits between the selected one and the decimal point. This is what I have called an omniscient Intangible Memory device. This is related to Stepthen Wolfram's Cellular Automatons in his book {New Kind of Science], except that the Intangible Memory functions require miniscule amounts of real memory to generate interesting and sometimes useful extremely long data strings.