Introducing
Prezi AI.
Your new presentation assistant.
Refine, enhance, and tailor your content, source relevant images, and edit visuals quicker than ever before.
Trending searches
Loading…
Copy of 비둘기집의 원리
Transcript
비둘기집의 원리
아래 그림 모양의 타일을 서로 다른 4가지 색으로 칠 할 수 있겠는가????(단 이웃하는 곳에 같은 색을 칠할 수 없다!!)
이와 같이 칠할 수 있다!!!!
비둘기집의 용례
아래 그림과 같이 10(n+1)마리의 비둘기가 9(n)개의 집에 들어갈때 적어도 한마리는 집에 들어가게 되는 걸 볼 수 있다
- 어느 그룹에 생일이 같은 사람이 반드시 1쌍 이상 존재한다고 말할 수 있으려면, 그 그룹의 인원은 367명 이상이어야 한다. 생일의 경우의 수는 2월29일을 포함하여 366가지 이기 때문이다.
- 앞이 보이지 않는 방에서 4쌍의 다른 양말이 널려 있을 때, 5개 이상의 양말을 고르면, 반드시 양말의 짝을 맞추어 신을 수 있다.
- 일반적인 사람의 머리카락 수는 15만 개이다. 그러므로 100만 개 이상 머리카락을 가진 사람은 없다고 가정해도 무리가 없다. 서울에는 1000만 명 가량의 사람이 있으므로, 서로 다른 머리카락의 개수를 서로 다른 비둘기집으로 보고, 서울에 사는 사람 각각을 머리카락의 개수에 따라 서로 다른 비둘기집에 할당하면, 같은 머리카락 개수를 가진 사람이 반드시 존재한다는 것을 알 수 있다.
비둘기집의 원리란?
비둘기집 원리는 n+1개의 물건을 n개의 상자에 넣을 때 적어도 어느 한 상자에는 두 개 이상의 물건이 들어 있다는 원리를 말한다. 보통 비둘기와 비둘기집의 형태로 비유되어 쓰이며, '서랍과 양말'로 비유하여 '서랍 원칙' 또는 '디리클레의 방 나누기 원칙'이라고 부르기도 한다.
- 일반화된 비둘기집의 원리
n개의 별개의 사물을 m개의 용기에 나누어 담으면 적어도 한 개의 용기는[n/m][ 이상의 사물을 담고 있어야 한다.
- 확률론적으로 본 비둘기집의 원리
1/m의 균일한 확률로 n개의 비둘기를 무작위로 m개의 비둘기집에 넣었다면 확률적으로 적어도 하나의 비둘기집에 두마리 이상의 비둘기가 들어가게 된다.
비둘기집의 원리의 증명
귀류법-
n개의 비둘기집과 n+1마리의 비둘기가 있다고 가정한다.
만약 각 비둘기집에 한 마리 이하의 비둘기만 들어 있다면, 전체 비둘기집에는 많아야 n마리의 비둘기가 존재한다. 그런데 비둘기는 모두 n+1마리이므로, 이것은 모순이다. 따라서 어느 비둘기집에는 두 마리 이상의 비둘기가 있다
Choose a template
Presentations from around the world
Learn more about creating dynamic, engaging presentations with Prezi