WELCOME TO THIS BLOG!!. PLEASE ENJOY THE MENU HAS BEEN PROVIDED

Selasa, 31 Mei 2011

The Pigeonhole Principle


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.


Anda sedang membaca artikel tentang The Pigeonhole Principle dan anda bisa menemukan artikel The Pigeonhole Principle ini dengan url 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.

Related Post



3 komentar:

Anas mengatakan...

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

Ridha Harwan mengatakan...

Wah hebat analisisnya....

Lubis Muzaki mengatakan...

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