Drs. Slamin, M.Comp.Sc.,Ph.D

Introduce by German Mathematician, Johann Peter GustavLejeune Dirichlet on 1834.

Also known as Dirichlet Drawer Principle.

**Theorem**

If n pigeons are assigned to m pigeonholes, and n > m, then there is pigeonhole contains at least two pigeons.

**Proof**

Prove by contradiction that the conclusion is not correct, so that every pigeonhole contains at most one pigeon. Since there are m pigeonholes, then at most m pigeons that can be contained. We know that there are n pigeons available and n > m, which is a contradiction.

**Example**

When lecturer divided students into six teams to do assignments, seven students did not attend the lecture so that they were not included in any team. Show that if the seven students join the team, then there are at least two students are in the same team!

**Solution**

Assume that the seven students are the pigeons, and the six teams are the pigeonholes. The Pigeonhole Principle tells us that there are at least two students must be assigned in the same team! Assume that the seven students are the pigeons, and the six teams are the pigeonholes. The Pigeonhole Principle tells us that there are at least two students must be assigned in the same team!

**Example**

A scholar in a village is always asked to provide a name for a new born baby. In certain month, he prepares 3 names for first names and 3 names for second names. 11 babies are born on that month. By assuming that the scholar always gives first name and second name for one baby, show that there are atleast two babies have the same name.

**Solution**

Combining first names and second names gives nine names. Assume that the nine names are the pigeonholes, and the eleven babies are the pigeons. The Pigeonhole Principle tells us that there are at least two babies must be assigned in the same name!

**Theorem**

If n pigeons are assigns to m pigeonholes, then one of the pigeonholes must contain at least ⌊n−1/m + 1⌋ pigeons.

**Proof**

If each pigeonhole contains no more than ⌊n−1/m ⌋ pigeons, then there are at most m · ⌊ n – 1/m ⌋ ≤ m·n− 1/m = n − 1

pigeons in all. This contradicts our assumptions, so one of the pigeonholes must contain at least

⌊n−1/m + 1⌋ pigeons.

**Example**

Show that if any 30 students are selected, then at least 5 of them will have been born in the same day of the week.

**solution**

Assign each student to the day of the week on which he or she was born. Then n = 30 pigeons are being assigned to m = 7 pigeonholes. By the extended pigeonhole principle, at least

⌊ n – 1/m+ 1⌋ = ⌊ 29/7 + 1⌋ = 5

of the students must have been born in the same day of the week.

**dan anda bisa menemukan artikel The Pigeonhole Principle ini dengan url**

__The Pigeonhole Principle__**http://zakylubismy.blogspot.com/2011/05/pigeonhole-principle.html**,anda boleh menyebar luaskannya atau mengcopy paste-nya jika artikel

**The Pigeonhole Principle**ini sangat bermanfaat bagi teman-teman anda,namun jangan lupa untuk meletakkan link

__The Pigeonhole Principle__sumbernya.

## 3 komentar:

waduh,, pembuktian teorema.. udah lama gak buka kitab analisis nih..

Wah hebat analisisnya....

mas anas: This article from my lecturer, Mr. Slamin.

mas Ridha Harwan : mr. slamin is master graph. about discrete mathematic. his blog mr. slamin : http:/slamin.blog.unej.ac.id

Poskan Komentar