비둘기집1 비둘기 집의 원리와 생일 문제 신은 주사위 놀이를 하지 않는다 10개의 공을 상자 9개에 넣는다면, 한 상자에는 적어도 공이 두 개 이상 있게 돼요. 이처럼 "n+1개의 물건을 n개의 상자에 넣으면 적어도 어느 한 상자에는 두 물건이 들어있다" 라는 원리를 비둘기 집의 원리라고 해요. 한 번 이 원리를 귀류법으로 증명해볼게요. 아래는 두 가지 가정이에요. ● n개의 비둘기 집과 n+1마리의 비둘기가 있다 ● 한 집에는 한 마리의 비둘기만 존재한다. 그럼 비둘기 집 전체에 n마리의 비둘기가 존재하게 돼요. 하지만 비둘기의 숫자는 n+1이죠. 가정에 모순이 생겼네요. 따라서 적어도 하나의 비둘기 집에는 두마리 이상의 비둘기가 있는 거죠. 생각보다 너무 간단하지 않나요? 내용도 쉬울뿐더러 증명도 쉽죠. 그리고 너무 당연한 사실이라 이름이나.. 2023. 3. 31. 이전 1 다음
